On the complexity of two machine job-shop scheduling with regular objective functions
On the complexity of two machine job-shop scheduling with regular objective functions
复制标题
DOI：
10.1007/bf01539799
复制
发表时间：
1997-03
期刊：
影响因子：
--
通讯作者：
P. Brucker;Svetlana A. Kravchenko;Y. Sotskov
中科院分区：
文献类型：
--
作者：
P. Brucker;Svetlana A. Kravchenko;Y. Sotskov
针对具有固定作业数量和目标函数Σfiand maxfi，其中作业完成时间为非递减函数的无抢占双机作业车间调度问题，给出了多项式算法。这回答了之前关于目标函数slmax、ΣwiUi和ΣwiU的相应问题的复杂性状态的开放性问题。我们推广了这些结果，证明了具有任何正则准则的问题都可以在多项式时间内求解。
For the nonpreemptive two machine job-shop scheduling problem with a fixed number of jobs and objective functions Σfiand maxfi, wherefiare nondecreasing functions of the finish times of jobsi, polynomial algorithms are presented. This answers previous open questions about the complexity status of the corresponding problems with objective functionsLmax, ΣwiUi, and ΣwiU. We generalize these results by showing that the problem with any regular criterion can be solved in polynomial time.