Necessary and sufficient conditions of optimality for some classical scheduling problems

作者：Lin Yixun^*; Wang Xiumei

来源：European Journal of Operational Research, 2007, 176(2): 809-818.

DOI：10.1016/j.ejor.2005.09.017

• scheduling problems
• optimality characterization
• critical jobs
• partial order

A scheduling problem is generally to order the jobs such that a certain objective function f(pi) is minimized. For some classical scheduling problems, only sufficient conditions of optimal solutions are concerned in the literature. In this paper, we study the necessary and sufficient conditions by means of the concept of critical ordering (critical jobs and their relations). These results are meaningful in recognition and characterization of optimal solutions of scheduling problems.

• 出版日期2007-1-16
• 单位郑州大学