研究相同工件在两台机器（分别称为机器M1和M2）上的混合流水作业问题，每个给定工件有两个任务，分别称之为任务A和任务B，任务B只能在任务A完工后才能开始加工，每个工件有两种加工模式供选择：模式1是将两个任务都安排在机器M2上加工；模式2是将任务A和B分别安排在机器M1和M2上加工.假设在加工工件时，机器具有学习效应，即工件的实际加工时间与工件的加工位置有关.目标函数是最小化最大完工时间.分别讨论了具有无缓冲区与无限缓冲区两种加工环境情况，两种情况下都得到了最优算法.
In this paper, optimal algorithms are proposed for hybrid flow shop schedule of identical jobs on two machines (named as M1 and M2) 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 M2. The second processing mode, named mode 2, is to assign task A and B to machine M1 and M2, 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.
[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.
