97-03
On Parallel Machine Scheduling Problems With a Single Server
by Kravchenko, S.A.; Werner, F.
Preprint series: 97-03, Preprints
The paper is published: Mathematical and Computer Modelling, Vol. 26, 1997, No. 12, 1 - 11.
Abstract: 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 singleserver. The objective is to minimize the schedule length (makespan) as wellas the forced idle time. The makespan problem is known to be NP -hardeven for the case of two identical parallel machines. This paper presentsa pseudopolynomial algorithm for the case of two machines when all setuptimes are equal to one. We also show that the more general problem withan arbitrary number of machines is unary NP -hard and analyze some listscheduling heuristics for this problem. The problem of minimizing the forcedidle time is known to be unary NP-hard for the case of two machines andarbitrary setup and processing times. We prove unary NP-hardness of thisproblem even for the case of constant setup times. Moreover, some polyno-mially solvable cases are given.
Keywords: production scheduling, parallel machine problems, setup times,NP-hard problems, polynomial algorithms, heuristics
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.