具有学习效应的两台机上最优混合流水作业算法

doi:10.15960/j.cnki.issn.1007-6093.2020.02.004

Abstract

Abstract: In this paper, optimal algorithms are proposed for hybrid flow shop schedule of identical jobs on two machines (named as M₁ and M₂) with learning effect. In our problem, each job has two tasks, named as task A and task B respectively, and two optional processing modes. The task B can start to be processed only if after task A has been finished. The first processing mode, named as mode 1, is to assign both task A and B to machine M₂. The second processing mode, named mode 2, is to assign task A and B to machine M₁ and M₂, respectively. It is assumed that each machine has learning effect when processing the job, in other words, the actual processing time of the job is related to the processing position of the job. Our objective is to minimize the makespan. Optimal algorithms are given for two systems with no buffer and infinite buffer respectively.

Key words: hybrid flow shop, learning effect, optimal algorithm, makespan

CLC Number:

O223

ZHAO Congcong, FANG Dandan, LI Rongheng. Optimal algorithms for hybrid flow shop schedule on two machines with learning effect[J]. Operations Research Transactions, 2020, 24(2): 42-60.

References

[1] Johnson S M. Optimal two-and three-stage production schedules with setup times included[J]. Naval Research Logistics Quarterly, 1954, 1(1):61-68.
[2] Garey M R, Sethi R.The complexity of flowshop and jobshop scheduling[J]. Mathematics of Operations Research, 1976, 1(1):117-129.
[3] Chen B, Glass c A, Potts c N, et al. A new heuristic for three machine flow shopscheduling[J]. Operations Research, 1996, 44(6):891-898.
[4] Panagiotis K, George V. Flowshops with processing flexibility across production stages[J]. IIE Transactions, 1998, 30:735-746.
[5] Wei Q, He Y. A two-stage semi-hybrid flowshop problem in graphics processing[J]. Applied Mathematics A Journal of Chinese Universities, 2005, 20:393-400.
[6] Wei Q, Shan EF, Kang LY. A FPTAS for a two-stage hybrid flow shop problem and optimal algorithms for identical jobs[J]. Theoretical Computer Science, 2014, 524:78-89.
[7] Qi Wei, Yong Wu, Yiwei Jiang, et al. Two-machine hybrid flowshop scheduling with identical jobs:Solution algorithms and analysis of hybrid benefits[J]. 2018, 817-826.
[8] 王芳, 饶运清. 柔性流水车间调度模型与混合引力算法[J]. 机械设计制造, 2016, 18(11):132-136.
[9] Hwang FJ, Lin BMT. Two-stage flexible flow shop scheduling subject to fixed job sequences[J]. Journal of the Operational Research Society, 2016, 67(3):506-515.
[10] Zhong WY, Shi Y. Two-stage no-wait hybrid flowshop scheduling with inter-stage flexibility[J]. Journal of Combinatorial Optimization, 2017, 35(2):1-18.
[11] Hsiao M C, Su L H. Scheduling of hybrid types of machines with two-machine flowshop as the first type and a single machine as the second type[J]. IOP Conference Series Materials Science and Engineering, 2018, 311:012008
[12] 刘洋, 唐恒永, 赵传立. 同时具有学习效应和退化效应的单机排序问题[J]. 运筹与管理, 2012, 21(3):81-86.
[13] Wright T P. Factors affecting the cost of airplanes[J]. Journal of the Aeronautical Sciences, 1936, 3(4):122-128.
[14] Biskup D. Single-machine scheduling with learning considerations[J]. European Journal of Operational Research, 1999, 115(1):173-178.
[15] Wang J B, Sun L H, Sun L Y. Scheduling jobs with an exponential sum-of-actual-processingtime-based learning effect[J]. Computers and Mathematics with Applications, 2010, 60(9):2673-2678.
[16] 王磊, 张玉忠, 王成飞. 机器具有学习效应的供应链排序问题[J]. 系统科学与数学, 2013, 33(7):799-806.
[17] Biskup D. A state-of-the-art review on scheduling with learning effects[J]. European Journal of Operational Research, 2008, 188(2):315-329.

Optimal algorithms for hybrid flow shop schedule on two machines with learning effect

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 10

Recommended Articles

Metrics

Comments

[1]	ZHAO Xiaocheng, LI Dagang. Parallel machine scheduling with machine and human eligibility restrictions [J]. Operations Research Transactions, 2018, 22(3): 99-108.
[2]	ZHU Zhenglu, LU Xiwen. Minimizing makespan on two parallel machines with learning effects [J]. Operations Research Transactions, 2018, 22(1): 55-66.
[3]	LIU Ying, ZHANG Xingong. Three-echelon supply chain scheduling problem with learning effect [J]. Operations Research Transactions, 2016, 20(1): 31-42.
[4]	LI Wenhua, CHAI Xing, YUAN Hang, YANG Sufang. On-line algorithms for incompatible job families on parallel machines scheduling with lookahead [J]. Operations Research Transactions, 2015, 19(4): 121-126.
[5]	JING Caixia, ZHAO Congli, YUAN Erming. A review of re-entrant scheduling problems [J]. Operations Research Transactions, 2015, 19(2): 37-44.
[6]	WAN Long. Two results for single-machine two-agent scheduling problems [J]. Operations Research Transactions, 2015, 19(2): 54-60.
[7]	WAN Long. An optimal algorithm for the two-order multiple problem [J]. Operations Research Transactions, 2014, 18(3): 99-103.
[8]	SHUAI Tianping,YU Jinguo,SUN Ling. A simulated annealing algorithm for the hybrid flow shop scheduling to minimize the number of tardy jobs [J]. Operations Research Transactions, 2013, 17(2): 41-47.
[9]	ZHANG Xingong. Single-machine group scheduling problems with the sum-of-processing-time based on learning effect [J]. Operations Research Transactions, 2013, 17(1): 98-105.
[10]	YANG Su-Fang, LI Wen-Hua. On-line scheduling on a machine of two families with lookahead [J]. Operations Research Transactions, 2012, 16(2): 115-120.