EARLINESS-TARDINESS SCHEDULING PROBLEMS .2. DEVIATION OF COMPLETION TIMES ABOUT A RESTRICTIVE COMMON DUE DATE

• 成果类型: Article
• 署名作者: HALL, NG; KUBIAK, W; SETHI, SP
• 署名单位: Memorial University Newfoundland; University of Toronto
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.39.5.847
• 发表日期: 1991
• 页码: 847-856
• 关键词: PRODUCTION SCHEDULING - DETERMINISTIC; SINGLE MACHINE SEQUENCING

摘要

A companion paper (Part I) considers the problem of minimizing the weighted earliness and tardiness of jobs scheduled on a single machine around a common due date, d, which is unrestrictively late. This paper (Part II) considers the problem of minimizing the unweighted earliness and tardiness of jobs, allowing the possibility that d is early enough to constrain the scheduling decision. We describe several optimality conditions. The recognition version of the problem is shown to be NP-complete in the ordinary sense, confirming a well known conjecture. Moreover, this complexity definition is precise, since we describe a dynamic programming algorithm which runs in pseudopolynomial time. This algorithm is also extremely efficient computationally, providing an improvement over earlier procedures, of almost two orders of magnitude in the size of instance that can be solved. Finally, we describe a special case of the problem which is polynomially solvable.