Preemptive Open-shop Scheduling: Network Flow based Algorithm

摘要：

Preemptive open-shop scheduling problem was studied, and a network flow based algorithm was presented. Firstly, based on the characteristics of the preemptive open-shop, the scheduling problem was formulated as a mixed-integer programming model with the objective to minimize the make-span. The maximum flow model of the preemptive open-shop was developed to model the machine resource allocation and time constraints. Moreover a new preflow push algorithm for the maximum flow model was put forward. Based on the solution of machine resource allocation problem got by preflow push algorithm, the sequences of the tasks processed by each machine were determined by calculating the matrix of the processing times and decrementing set. Finally, the validity of the developed scheduling algorithm is illustrated by randomly generated example.

关键词： Preemptive open-shop scheduling Makespan Network flow

作者: Y.Zhan Y.G.Zhong H.T.Zhu

作者单位: College of Mechanical & Electrical Engineering, Harbin Engineering University, Heilongjiang, Harbin, 150001, China

会议类型: 国际会议

会议名称: 2011 Global Conference on Digital Design and Manufacturing Technology(2011年全国数字设计与制造技术会议)

会议地点: 杭州

会议语种:英文

页码: 111-114

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