by Kravchenko, S.A., Werner, F..

**Series:** 1997-03, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic

**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 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.

**Keywords:**

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.