Due‐date assignment and early/tardy scheduling on identical parallel machines

Prabuddha De, Jay B. Ghosh and Charles E. Wells

Naval Research Logistics (NRL), 1994, vol. 41, issue 1, 17-32

Abstract: This article examines the problem of simultaneously assigning a common due date to a set of independent jobs and scheduling them on identical parallel machines in such a way that the costs associated with the due date and with the earliness or tardiness of the jobs are minimized. We establish that, for certain values of the due‐date cost, an optimal schedule for this problem is also optimal for an early/tardy scheduling problem studied by Emmons. We discuss the solution properties for the two problems, and show that both problems are NP‐hard even for two machines. We further show that these problems become strongly NP‐hard if the number of machines is allowed to be arbitrary. We provide a dynamic programming solution for the problems, the complexity of which indicates that the problems can be solved in pseudopolynomial time as long as the number of machines remains fixed. Finally, we present the results of a limited computational study. © 1994 John Wiley & Sons, Inc.

Date: 1994
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199402)41:13.0.CO;2-X

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:41:y:1994:i:1:p:17-32

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 ().