by Kravchenko, S.A., Werner, F..
Series: 1997-03, Preprints
In this paper we consider the problem of scheduling jobs on par-
allel machines with setup times. The setup has to be performed by a single
server. The objective is to minimize the schedule length (makespan) as well
as the forced idle time. The makespan problem is known to be NP -hard
even for the case of two identical parallel machines. This paper presents
a pseudopolynomial algorithm for the case of two machines when all setup
times are equal to one. We also show that the more general problem with
an arbitrary number of machines is unary NP -hard and analyze some list
scheduling heuristics for this problem. The problem of minimizing the forced
idle time is known to be unary NP-hard for the case of two machines and
arbitrary setup and processing times. We prove unary NP-hardness of this
problem even for the case of constant setup times. Moreover, some polyno-
mially solvable cases are given.
production scheduling, parallel machine problems, setup times,NP-hard problems, polynomial algorithms, heuristics
This paper was published in:
Mathematical and Computer Modelling, Vol. 26, 1997, No. 12, 1 - 11.