Model and Algorithm of Paravlel Multiprocessor Open Shop Scheduling Problem

Abstract

Abstract: Grain sorting scheduling problem in LED manufacturing was a typical multiprocessor open shop scheduling problem，which belonged to NP-hard problem.Model and algorithm for solving this kind of scheduling problems with the objective of minimizing total weighted completion time were studied herein.According to the characteristics of the problem，a mixed integer-programming model was constructed to obtain the optimal solution，and a heuristic algorithm and an improved particle swarm optimization algorithm were designed.Simulation results show that both heuristic algorithm and improved particle swarm optimization algorithm may obtain good scheduling solutions quickly and effectively in a reasonable time.

Key words: open shop scheduling problem, light emitting diode (LED), weighted completion time, modified particle swarm optimization, grain sorting

摘要： 发光二极管制造过程中，晶粒分类拣选工序的调度问题是典型的并行多机开放车间调度问题，属于NP-hard问题。研究了该调度问题以最小化总加权完工时间为目标的求解模型与算法。根据问题特性构建了可获得最优解的混合整数规划模型，并设计了同时考虑质量与求解效率的启发式算法和改进粒子群优化算法。仿真结果显示，启发式算法和改进粒子群优化算法都能在合理的时间内迅速有效地获得较佳的调度解。

关键词: 开放车间调度问题, 发光二极管, 加权完工时间, 改进粒子群优化算法, 晶粒分类拣选

CLC Number:

F224

CHEN YarongHUANG PeiyuLI PeiCHOU FuhderHUANG Shengquan. Model and Algorithm of Paravlel Multiprocessor Open Shop Scheduling Problem[J]. China Mechanical Engineering.

陈亚绒, 黄佩钰, 李沛, 周富得, 黄沈权. [车间调度]并行多机开放车间调度问题的模型与算法[J]. 中国机械工程.

References

[1]ANAND E，PANNEERSELVAM R.Literature Review of Open Shop Scheduling Problems[J].Intelligent Information Management，2015，7(1):33-52.
[2]NADERI B，GHOMI S M T F，AMINNAYERI M，et al.Scheduling Open Shops with Parallel Machines to Minimize Total Completion Time[J].Journal of Computational and Applied Mathematics，2011，235(5): 1275-1287.
[3]ABDELMAGUID T F，SHALABY M A，AWWAD M A.A Tabu Search Approach for Proportionate Multiprocessor Open Shop Scheduling [J].Computational Optimization & Applications，2014，58(1): 187-203.
[4]SHIANG W J，LIN Y H，RAU H.Application of Simulation to the Scheduling Problem for a LED Sorting System[C]//IEEE International Conference on Machine Learning and Cybernetics.Baoding，China: ICMLC，2009: 2875-2879.
[5]ROEMER T A.A Note on the Complexity of the Concurrent Open Shop Problem[J].Journal of Scheduling，2006，9(4): 389-396.
[6]BRSEL H，HERMS A，MRIG M，et al.Heuristic Constructive Algorithms for Open Shop Scheduling to Minimize Mean Flow Time[J].European Journal of Operational Research，2008，189(3): 856-870.
[7]TANG L，BAI D.A New Heuristic for Open Shop Total Completion Time Problem[J].Applied Mathematical Modelling，2010，34(3):735-743.
[8]AHMADIZAR F，FARAHANI M H.A Novel Hybrid Genetic Algorithm for the Open Shop Scheduling Problem[J].International Journal of Advanced Manufacturing Technology，2012，62(5/8):775-787.
[9]NADERI B，FATEMI GHOMI S M T，AMINNAYERI M，et al.A Study on Open Shop Scheduling to Minimize Total Tardiness [J].International Journal of Production Research，2011，49(15): 4657-4678.
[10]王军强,郭银洲,崔福东,等.基于多样性增强的自适应遗传算法的开放式车间调度优化[J].计算机集成制造系统，2014，20(10):2479-2493.
WANG Junqiang，GUO Yinzhou，CUI Fudong，et al.Diversity Enhancement-based Adaptive Genetic Algorithm for Open-shop Scheduling Problem[J].Computer Integrated Manufacturing System，2014，20(10): 2479-2493
[11]HUANG Y M，LIN J C.A New Bee Colony Optimization Algorithm with Idle-time-based Filtering Scheme for Open Shop-scheduling Problems[J].Expert Systems with Applications，2011，38(5):5438-5447.
[12]高亮,高海兵,周驰.基于粒子群优化的开放式车间调度[J].机械工程学报，2006，42(2):129-134.
GAO Liang，GAO Haibin，ZHOU Chi.Open Shop Scheduling Based on Particle Swarm Optimization [J].Chinese Journal of Mechanical Engineering，2006，42(2): 129-134.
[13]SHA D Y，HSU C Y.A New Particle Swarm Optimization for the Open Shop Scheduling Problem [J].Computers & Operations Research，2008，35(10):3243-3261.
[14]NASIRI M M，YAZDANPARAST R，JOLAI F.Simulation Optimization Approach for Optimizing Jobs Dispatching Rule in an Open Shop Scheduling Problem[J].International Journal of Computer Integrated Manufacturing，2017，30(46):1239-1252.
[15]BAI D，ZHANG Z，ZHANG Q.Flexible Open Shop Scheduling Problem to Minimize Makespan[J].Computers & Operations Research，2015，67(1): 207-215.
[16]WANG W L，WANG H Y，ZHAO Y W，et al.Parallel Machine Scheduling with Splitting Jobs by a Hybrid Differential Evolution Algorithm[J].Computers & Operations Research，2013，40(5):1196-1206.
[17]MATTA M E.A Genetic Algorithm for the Proportionate Multiprocessor Open Shop[J].Computers & Operations Research，2009，36(9): 2601-2618.
[18]CHEN Y，ZHANG A，CHEN G，et al.Approximation Algorithms for Parallel Open Shop Scheduling[J].Information Processing Letters，2013，113(7):220-224.
[19]展勇,邱长华,祝海涛.基于网络流的多并行机可中断开放车间调度算法[J].计算机集成制造系统，2011，17(5): 990-996.
ZHAN Yong，QIU Changhua，ZHU Haitao.An Interruptible Multiprocessor Open Shop Scheduling Algorithm Based on Network Flow [J].Computer Integrated Manufacturing System，2011，17(5):990-996.
[20]BEAN J.Genetic Algorithms and Random Keys for Sequencing and Optimization[J].Orsa Journal on Computing，1994，6:154-160.