Fixed job schedule problem with working-time constraints

We considere 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 brach-and-bound algorithm for optimal solution of the problem. The effectiveness of the algorithm is analyzed through computational experiments.