The Fixed Job Schedule Problem with Working-Time Constraints
Matteo Fischetti, Silvano Martello, Paolo Toth
Operations Research · 1989 · Volume 37 · Issue 3
Abstract
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.
Keywords
production/scheduling: fixed job scheduling, programming, algorithms, branch-and-bound: lower bounds
Enable JavaScript for citation tools and additional paper interactions.