zbMATH — the first resource for mathematics

The fixed job schedule problem with working-time constraints. (English) Zbl 0672.90074
Summary: 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.

90B35 Deterministic scheduling theory in operations research
68Q25 Analysis of algorithms and problem complexity
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Full Text: DOI