The Fixed Job Schedule Problem with Working-Time Constraints
研究在处理器总工作时间受限下的固定作业调度问题，证明该问题NP难但可抢占情形可多项式求解，提出下界并设计分支定界算法，通过实验验证有效性。
We consider a generalization of the fixed job schedule problem where a bound is imposed on the total working time of each processor. It is shown that the problem is NP-hard but polynomially solvable in the preemptive case. We introduce several lower bounds. One is determined through definition of a special class of graphs, for which the maximum clique problem is shown to be polynomial. Lower bounds and dominance criteria are exploited in a branch-and-bound algorithm for optimal solution of the problem. The effectiveness of the algorithm is analyzed through computational experiments.