Computer Science ›› 2016, Vol. 43 ›› Issue (9): 18-22.doi: 10.11896/j.issn.1002-137X.2016.09.003

Previous Articles     Next Articles

Complexity of Flow Shop Scheduling Problems with No-load Return Transportation

LAN Yan, ZHANG Ming-hui, WU Zong-tao and HAN Xin   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Flow shop is one of the most classic scheduling problems.The model of a flow shop problem with two machines and a transporter which can transport a job from machine 1(M1) to machine 2(M2) every time is widely applied in most manufacturing systems.In this paper,the no-load return transportation time from machine M2 to M1 was consi-dered,and we assumed that it equals with the time from M1 to M2.Then we showed that the NP-complete problem 3-PARTITION is reducible to an instance of the problem we researched,so that we can demonstrate that this problem is a NP-hard problem in the strong sense.

Key words: Flow-shop problems,No-load return transportation,Scheduling,Complexity

[1] Lawler E L,Lenstra J K,Kan A H G R,et al.Sequencing and scheduling:Algorithms and complexity [J].Handbooks in Ope-rations Research and Management Science,1993,4(2):445-522
[2] Garey M R,Johnson D S,Sethi R.The complexity of flow shop and job shop scheduling [J].Math Ops Res,1976,1(2):117-129
[3] Taillard E.Some efficient heuristic methods for the flow shopsequencing problem [J].European Journal of Operational Research,1990,47(1):65-74
[4] Reeves C R.A genetic algorithm for flow shop sequencing[J].Computers & Operations Research,1995,22(1):5-13
[5] Chen Xiong,Tang Guang-qiang,Wu Qi-di.Study of three ma-chine flow-shop scheduling problem[J].Information and Control,2008,1(3):211-215(in Chinese) 陈雄,汤光强,吴启迪.3机Flow-shop调度问题研究[J].信息与控制,2008,31(3):211-215
[6] Yang Liu,Hu Zhi-gang,Long Jun.Optimization Algorithm forBatch Scheduling in Flow Shop[J].Journal of Chinese Computer Systems,2012,33(6):1333-1336(in Chinese) 杨柳,胡志刚,龙军.流水作业批调度问题优化算法研究[J].小型微型计算机系统,2012,33(6):1333-1336
[7] Liu Ying,Gu Wen-xiang,Li Xiang-tao.Research on Permuta-tion Flow-shop Scheduling Problem[J].Computer Science,2013,40(11):1-7(in Chinese) 刘莹,谷文祥,李向涛.置换流水线车间调度问题的研究[J].计算机科学,2013,40(11):1-7
[8] Liu Yan-feng,Liu San-yang.Permutation flow shop scheduling algorithm based on ant colony optimization[J].Computer Applications,2008,28(2):302-304(in Chinese) 刘延风,刘三阳.置换流水车间调度的蚁群优化算法[J].计算机应用,2008,28(2):302-304
[9] Li Xiao-bin,Bai Yan,Geng Lin-xiao.Improved genetic algorithm for solving permutation flow shop scheduling problem[J].Computer Applications,2013,33(12):3576-3579(in Chinese) 李小缤,白焰,耿林霄.求解置换流水车间调度问题的改进遗传算法[J].计算机应用,2013,33(12):3576-3579
[10] Chen Cheng-dong,Chen Hua-ping,Zhu Qi,et al.Ant Colony Optimization Algorithm for Batch Scheduling Problem of Two-stage Flow Shop[J].Computer Engineering,2012,38(19):137-141(in Chinese) 陈成栋,陈华平,朱颀,等.两阶段流水车间批调度问题的蚁群优化算法[J].计算机工程,2012,38(19):137-141
[11] Shi Ling,Wen Jun.Flow-shop Scheduling Problem with Transportation Times and a Single Robot[J].Acta Mathematica Scien-tia,2008,8(5):967-970(in Chinese) 时凌,文军.带运输时间和自动机的流水作业排序问题的复杂性[J].数学物理学学报,2008,28(5):967-970
[12] Lee C Y,Chen Z L.Machine scheduling with transportation considerations [J].Journal of Scheduling,2001,4:3-24
[13] Kise H,Shioyama T,Ibaraki T.Automated two-machine Flowshop scheduling:a solvable case[J].IIE Transactions,1991,23(1):10-16
[14] Hurink J,Knust S.Makespan minimization for flow-shop problems with transportation times and a single robot [J].Discrete Applied Mathematics,2001,112(1):199-216
[15] Chen Ke-jia,Wang Xiao.Properties of two-machine no-waitflowshop scheduling problems[J].Control and Decision,2013,8(10):1502-1506(in Chinese) 陈可嘉,王潇.两机无等待流水车间调度问题的性质[J].控制与决策,2013,28(10):1502-1506
[16] Chen Bai-long.Two parallel machines scheduling with one avai-lability constraint and jobs with delivery times[J].Journal of Lanzhou University(Natural Sciences),2009,45(4):140-146(in Chinese) 陈伯龙.带运输时间和一个不可用约束的两台平行机排序[J].兰州大学学报(自然科学版),2009,45(4):140-146
[17] Zhang Cui-lin,Wang Shuo,Wang Jun-qiang.Research on Flexible Flow Shop Scheduling with Relaxation Constrains[J].Machine Design and Manufacturing Engineering,2014(5):39-44(in Chinese) 张翠林,王烁,王军强.考虑约束松弛的柔性流水调度研究[J].机械设计与制造工程,2014(5):39-44
[18] Chen Ke-jia,Wang Xiao.Property of solving two-machine flow shop scheduling with unavailable interval[J].Journal of Nanjing University of Science and Technology,2015,39(2):202-205(in Chinese) 陈可嘉,王潇.机器具有不可用时间间隔的两机流水车间调度问题求解性质[J].南京理工大学学报(自然科学版),2015,39(2):202-205
[19] Garey M R,Johnson D S.Computers and Intractability:A Guide to the Theory of NP-Completeness [M].Wh Freeman & Company,1979

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!