Due‐date assignment and early/tardy scheduling on identical parallel machines
作者:
Prabuddha De,
Jay B. Ghosh,
Charles E. Wells,
期刊:
Naval Research Logistics (NRL)
(WILEY Available online 1994)
卷期:
Volume 41,
issue 1
页码: 17-32
ISSN:0894-069X
年代: 1994
DOI:10.1002/1520-6750(199402)41:1<17::AID-NAV3220410103>3.0.CO;2-X
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractThis 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&Son
点击下载:
PDF
(870KB)
返 回