Approximation algorithms for fixed job schedule problems

The authors consider two generalizations of the fixed job schedule problem, obtained by imposing a bound on the spread-time or on the working time of each processor. These NP-hard problems, studied by them in previous works, can arise in bus driver scheduling. The authors introduce several polynomial-time approximation algorithms, give efficient implementations for them, and analyze their complexity and worst case performance. The average behavior is also investigated through extensive computational experiments.