Open shop problem with zero-one time operations and integer release date deadline intervals

作     者：Kubale, M 

作者机构：Department of Foundations of Informatics Technical University of Gdansk Narutowicza 11/12 80-952 Gdansk Poland 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：1997年第76卷第1-3期

页      面：213-223页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：bipartite graph deadline edge-coloring NP-completeness open-shop polynomial algorithm release date scheduling 

摘      要：We study the problem of constructing a minimum makespan schedule for the n-job m-machine open shop with zero-one time operations and integer release dates and deadlines. The general scheduling problem is shown to be NP-complete. Two polynomial-time algorithms are given for the following special cases: (1) all possible mn operations have unit execution time, and (2) at most m+n operations have unit execution time. Next, the second algorithm is generalized to bounded cyclicity graphs. All the algorithms are capable of minimizing not only makespan but maximum lateness and maximum tardiness as well.