Scheduling parallel machines with a single server

Author

Xie Xie ; Huibo Zhou ; Yanping Li ; Yongyue Zheng

Author_Institution

Key Lab. of Manuf. Ind. & Integrated Autom., Shenyang Univ. Shenyang, Shenyang, China

Volume

1

fYear

2012

fDate

18-20 May 2012

Firstpage

453

Lastpage

456

Abstract

This paper investigates scheduling parallel machines with a single sever as well as additional constraints on setups and removals. It generalizes classical parallel machine scheduling problem with a single server which needs to perform setup operation of each job only. This model is motivated by a key course of batch annealing process in the steel industry: heating or cooling. The objective is to minimize makespan. For this problem, we first give some complexity results by reduction. Some optimal properties are derived. Based on the properties, a LPT heuristics is proposed which generates a tight worst-case bound 3/2-1/2m.

Keywords

computational complexity; cooling; single machine scheduling; steel industry; LPT heuristics; batch annealing process; classical parallel machine scheduling problem; cooling; heating; makespan minimization; optimal properties; setup operation; single server; steel industry; tight worst-case bound; Automation; Standardization; NP-hard problem; parallel machines; ratio performance; single server;

fLanguage

English

Publisher

ieee

Conference_Titel

Measurement, Information and Control (MIC), 2012 International Conference on

Conference_Location

Harbin

Print_ISBN

978-1-4577-1601-0

Type

conf

DOI

10.1109/MIC.2012.6273340

Filename

6273340