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

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

运筹学学报 ›› 2020, Vol. 24 ›› Issue (2): 42-60.doi: 10.15960/j.cnki.issn.1007-6093.2020.02.004

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

赵聪聪, 方丹丹, 李荣珩^*

计算与随机数学教育部重点实验室, 湖南师范大学数学与统计学院, 长沙 410081

收稿日期:2020-01-11 发布日期:2020-06-13
通讯作者: 李荣珩 E-mail:lirongheng@hunnu.edu.cn
基金资助:
国家自然科学基金（No.11471110），湖南省教育厅重点课题（No.16A126）

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

ZHAO Congcong, FANG Dandan, LI Rongheng^*

Key Laboratory of High Performance Computing and Stochastic Information Processing, School of Mathematics Statistics, Hunan Normal University, Changsha 410081, China

Received:2020-01-11 Published:2020-06-13

摘要/Abstract

摘要： 研究相同工件在两台机器（分别称为机器M₁和M₂）上的混合流水作业问题，每个给定工件有两个任务，分别称之为任务A和任务B，任务B只能在任务A完工后才能开始加工，每个工件有两种加工模式供选择：模式1是将两个任务都安排在机器M₂上加工；模式2是将任务A和B分别安排在机器M₁和M₂上加工.假设在加工工件时，机器具有学习效应，即工件的实际加工时间与工件的加工位置有关.目标函数是最小化最大完工时间.分别讨论了具有无缓冲区与无限缓冲区两种加工环境情况，两种情况下都得到了最优算法.

关键词: 混合流水作业, 学习效应, 最优算法, 最大完工时间

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

中图分类号:

O223

赵聪聪, 方丹丹, 李荣珩. 具有学习效应的两台机上最优混合流水作业算法[J]. 运筹学学报, 2020, 24(2): 42-60.

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.

参考文献

[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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

本文评价

[1]	朱征露, 鲁习文. 带学习效应的两台平行机时间表长问题[J]. 运筹学学报, 2018, 22(1): 55-66.
[2]	刘颖, 张新功. 具有学习效应的三层供应链排序问题[J]. 运筹学学报, 2016, 20(1): 31-42.
[3]	李文华, 柴幸, 袁航, 杨素芳. 平行机上带有前瞻区间的不相容工件组在线排序问题[J]. 运筹学学报, 2015, 19(4): 121-126.
[4]	井彩霞, 赵聪俐, 袁二明. 重入排序问题综述[J]. 运筹学学报, 2015, 19(2): 37-44.
[5]	万龙. 有关单机两代理排序问题的两个结果[J]. 运筹学学报, 2015, 19(2): 54-60.
[6]	万龙. 二阶数乘问题的一个最优算法[J]. 运筹学学报, 2014, 18(3): 99-103.
[7]	张新功. 基于加工时间之和学习效应下的单机成组排序问题[J]. 运筹学学报, 2013, 17(1): 98-105.
[8]	杨素芳, 李文华. 具有前瞻区间的两个工件组单机在线排序问题[J]. 运筹学学报, 2012, 16(2): 115-120.
[9]	仲维亚, 刘晓蕾, 霍志明. 工件可转包加工的排序问题研究[J]. 运筹学学报, 2012, 16(1): 121-128.