Abstract
In this paper, we consider the problem of scheduling a set of jobs having only two possible processing times on a set of unrelated parallel machines. This problem is a generalisation of the much more common problem of scheduling equal-length jobs on identical machines. Such a situation may occur in the production of two different types of products. First, we show that an earlier open problem of scheduling jobs with two possible processing times and
on unrelated machines with the objective to minimise the makespan can be polynomially solved by an algorithm consisting of two phases. A slight modification of this algorithm yields an absolute worst-case error of
for the case of two arbitrary processing times
and
,
. Thus, for practical problems of a large size with two types of products and two possible processing times, the approximation algorithm generates schedules very close to an optimal one.
Acknowledgments
The authors are also grateful to Elena Vakhania for her kind participation in the construction of the examples given in Section 5.
Notes
The first author was supported by Deutscher Akademischer Austauschdienst (DAAD) and by CONACyT [grant number 160162].