Scheduling Parallel Machines with a Single Server

摘要：

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/2/m.

关键词： parallel machines single server NP-hard problem ratio performance

作者: Xie Xie Yanping Li Huibo Zhou Yongyue Zheng

作者单位: Key Laboratory of Manufacturing Industrial and Integrated Automation, Shenyang University Shenyang, School of mathematical science, Harbin normal University Harbin, China Liaoning Institute of standardization, Shenyang, China

会议类型: 国际会议

会议名称: 2012 International Conference on Measurement,Information and Control(2012测量、信息与控制国际会议 ICMIC2012)

会议地点: 哈尔滨

会议语种:英文

页码: 453-456

在线出版日期: 2012-05-18（万方平台首次上网日期，不代表论文的发表时间）