Scheduling on parallel machines with servers

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


Preprint series: 98-30, Preprints

90B35 Scheduling theory, See also {68M20}


Abstract: In this paper, we consider the problem of scheduling a set of jobs on a set of identical parallel machines. Before the processing of a job can start, a setup is required which has to be performed by one server of a given set of available servers. We consider the complexity of such problems for the minimization of makespan. For the problem with unit setup times, m machines and m-1 servers, we give a pseudopolynomial algorithm. However, the problem with fixed number of machines and servers in the case of minimizing maximum lateness is proven to be unary NP-hard. Moreover, we perform a worst-case analysis of two list scheduling algorithms for makespan minimization.

Keywords: Parallel machine scheduling, setup times, NP-hard problems, pseudopolynomial algorithm, flexible manufacturing

The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster