Heuristics for multimachine minmax scheduling problems with general earliness and tardiness costs

Awi Federgruen and Gur Mosheiov

Naval Research Logistics (NRL), 1997, vol. 44, issue 3, 287-299

Abstract: We consider the problem of scheduling N jobs on M parallel machines so as to minimize the maximum earliness or tardiness cost incurred for each of the jobs. Earliness and tardiness costs are given by general (but job‐independent) functions of the amount of time a job is completed prior to or after a common due date. We show that in problems with a nonrestrictive due date, the problem decomposes into two parts. Each of the M longest jobs is assigned to a different machine, and all other jobs are assigned to the machines so as to minimize their makespan. With these assignments, the individual scheduling problems for each of the machines are simple to solve. We demonstrate that several simple heuristics of low complexity, based on this characterization, are asymptotically optimal under mild probabilistic conditions. We develop attractive worst‐case bounds for them. We also develop a simple closed‐form lower bound for the minimum cost value. The bound is asymptotically accurate under the same probabilistic conditions. In the case where the due date is restrictive, the problem is more complex only in the sense that the set of initial jobs on the machines is not easily characterized. However, we extend our heuristics and lower bounds to this general case as well. Numerical studies exhibit that these heuristics perform excellently even for small‐ or moderate‐size problems both in the restrictive and nonrestrictive due‐date case. © 1997 John Wiley & Sons, Inc.

Date: 1997
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://doi.org/10.1002/(SICI)1520-6750(199704)44:33.0.CO;2-4

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:44:y:1997:i:3:p:287-299

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().