Minimization of earliness, tardiness and due date penalties on uniform parallel machines with identical jobs
- Authors
- Drobouchevitch, Inna G.; Sidney, Jeffrey B.
- Issue Date
- 9월-2012
- Publisher
- PERGAMON-ELSEVIER SCIENCE LTD
- Keywords
- Parallel machine scheduling; Common due date; Earliness; Tardiness
- Citation
- COMPUTERS & OPERATIONS RESEARCH, v.39, no.9, pp.1919 - 1926
- Indexed
- SCIE
SCOPUS
- Journal Title
- COMPUTERS & OPERATIONS RESEARCH
- Volume
- 39
- Number
- 9
- Start Page
- 1919
- End Page
- 1926
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/107597
- DOI
- 10.1016/j.cor.2011.05.012
- ISSN
- 0305-0548
- Abstract
- We consider a problem of scheduling n identical nonpreemptive jobs with a common due date on in uniform parallel machines. The objective is to determine an optimal value of the due date and an optimal allocation of jobs onto machines so as to minimize a total cost function, which is the function of earliness, tardiness and due date values. For the problem under study, we establish a set of properties of an optimal solution and suggest a two-phase algorithm to tackle the problem. First, we limit the number of due dates one needs to consider in pursuit of optimality. Next, we provide a polynomial-time algorithm to build an optimal schedule for a fixed due date. The key result is an O(m(2) log m) algorithm that solves the main problem to optimality. Scope and purpose: To extend the existing research on cost minimization with earliness, tardiness and due date penalties to the case of uniform parallel machines. (C) 2011 Elsevier Ltd. All rights reserved.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - Graduate School > Department of Business Administration > 1. Journal Articles
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.