• 《工程索引》(EI)刊源期刊
  • 中文核心期刊(综合性理工农医类)
  • 中国科技论文统计源期刊
  • 中国科学引文数据库来源期刊

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

带有限缓冲区的混合流水车间多目标调度

袁庆欣 董绍华

袁庆欣, 董绍华. 带有限缓冲区的混合流水车间多目标调度[J]. 工程科学学报. doi: 10.13374/j.issn2095-9389.2020.02.26.002
引用本文: 袁庆欣, 董绍华. 带有限缓冲区的混合流水车间多目标调度[J]. 工程科学学报. doi: 10.13374/j.issn2095-9389.2020.02.26.002
YUAN Qing-xin, DONG Shao-hua. Optimizing multi-objective scheduling problem of hybrid flow shop with limited buffer[J]. Chinese Journal of Engineering. doi: 10.13374/j.issn2095-9389.2020.02.26.002
Citation: YUAN Qing-xin, DONG Shao-hua. Optimizing multi-objective scheduling problem of hybrid flow shop with limited buffer[J]. Chinese Journal of Engineering. doi: 10.13374/j.issn2095-9389.2020.02.26.002

带有限缓冲区的混合流水车间多目标调度

doi: 10.13374/j.issn2095-9389.2020.02.26.002
基金项目: 国家自然科学基金资助项目(71301008)
详细信息
    通讯作者:

    E-mail:15522625919@163.com

  • 中图分类号: U673.2

Optimizing multi-objective scheduling problem of hybrid flow shop with limited buffer

More Information
  • 摘要: 研究对象是带有限缓冲区混合流水车间中的多目标调度问题。以各机器前置后置缓冲区容积有限、工件以批量形式运输、运载设备的运载能力有限等作为资源限制因素,以最小化完工时间、最小化物料运输时间、最小化并行机前置缓冲区空间占用率均衡指数为目标,建立调度模型。分别采用NSGA-II、NSGA-III算法求解该模型,并对比两者之间的差别;设置不同的缓冲区容积,探究不同缓冲区容积对生产目标的影响,寻找最优缓冲区容积;建立不同模型,探究以最小化并行机前置缓冲区空间占用率均衡指数为目标的意义,最后以某船用管类生产企业的实际生产案例作为对象,通过对比优化结果与实际生产数据,验证了算法有效性。

     

  • 图  1  编码示意图(a)与交叉示意图(b)

    Figure  1.  Coding diagram (a) and cross diagram (b)

    图  2  生产车间布局图

    Figure  2.  Production workshop layout

    图  3  NSGA-II(a)与NSGA-III(b)优化结果图

    Figure  3.  NSGA-II (a) and NSGA-III (b) optimization results

    图  4  NSGA-II与NSGA-III一级个体数量对比图

    Figure  4.  Comparison of the number of NSGA-II and NSGA-III individuals

    图  5  优化3目标有限缓冲区的混合流水车间调度模型三指标统计结果

    Figure  5.  Three statistical results of hybrid flow shop scheduling model with optimized three-object limited buffer zone

    图  6  模型1与模型2对比。(a)完工时间;(b)运输时间;(c)缓冲区均衡指数

    Figure  6.  Comparison of model 1 and model 2: (a) completion time; (b) transportation time; (c) buffer equilibrium index

    表  1  参数及变量设计

    Table  1.   Design of the parameters and decision variables

    ParametersDescription
    $C_{s,k}^{\rm{F}}$Capacity of the kth machine’s front buffer in the stage s
    $C_k^{\rm{B}}$Capacity of the kth machine’s back buffer
    ${N_s}$Number of machines at the s processing stage
    ${J_a}$Total number of artifacts in batch a
    $T_{s,k,j}^{\rm{C}}$Completion time of job $j$ on the kth machine belong to sth stage
    $T_{i,s \to (s + 1),j}^{}$Transportation completion time of ith transporter for transports job $j$
    $T_{s,k,j}^{\rm{s}}$Starting time of job $j$ that processed on the kth machine belong to sth stage
    $t_{_{s,k,j}}^{\rm{p}}$The processing time of job $j$ on the kth machine belong to sth stage
    ${t_{i,s \to (s + 1),j}}$The transportation time of ith transporter for transports job $j$
    $T_{i,s \to (s + 1),j}^{\rm{l}}$The leaving time of job $j$ that leaves ith transporter
    $T_{s,k}^{\rm{i}}$The idle time of the kth machine belong to sth stage
    $T_{s,k,j}^{\rm{l}}$The leaving time of job $j$ that leaves the kth machine belong to sth stage s
    $T_{s,k,{\rm{B}},j}^{\rm{l}}$The leaving time of job $j$ that leaves back buffer of the kth machine belong to sth stage
    $T_{a,s,k}^{\rm{l}}$The leaving time of ath batch that leaves the kth machine belong to sth stage
    $T_{i,s \to (s + 1),k}^{\rm{a}}$The arriving time of ith transporter that arrives the kth machine belong to sth stage
    $V_{s,k}^{\rm{B}}$The remaining volume of the back buffer of the kth machine belong to sth stage
    $V_{s,k}^{\rm{F}}$The remaining volume of the front buffer of the kth machine belong to sth stage
    $T_{j,s,k}^{\rm{B}}$The last time the back buffer of the kth machine has enough room for job $j$
    $T_{(s + 1),k,a}^{\rm{F}}$The last time the front buffer of the kth machine has enough room for batch a
    $T_{j,s,k}^{\rm{B}}$The moment that the back buffer of the kth machine has enough room for job $j$
    $T_{a,s,k}^{\rm{F}}$The moment that the front buffer of the kth machine has enough room for batch a
    $t$Production moment
    ${X_{i,s \to (s + 1),j,t}}$If job $j$ is transported by transporter ith transporter at $t$, it is equal to 1, otherwise 0
    ${X_{k,j,t}}$If job $j$ is processed on the kth machine at $t$, it is equal to 1, otherwise 0
    ${X_{j,s,k,{\rm{F}},t}}$If job $j$ is in the front buffer of the kth machine belong to sth stage at $t$, it is equal to 1, otherwise 0
    ${X_{j,k,{\rm{B}},t}}$If job $j$ is in the back buffer of the kth machine at $t$, it is equal to 1,otherwise 0
    ${X_{i,s \to (s + 1),a,t}}$If ath transported by ith transporter t, it is equal to 1, otherwise 0
    下载: 导出CSV

    表  2  工件编号以及对应各阶段机器适用状况统计表

    Table  2.   Workpiece number and statistics of applicable conditions of the machine at each stage

    Job numberCuttingBendingSpot-weldingFully-weldingPolishingPumping
    1[1,2][6,7][16,17][18,19][20,21][22]
    2[3,4,5][8][16,17][18,19][20,21][22]
    3[3,4,5][9][16,17][18,19][20,21][22]
    4[3,4,5][10][16,17][18,19][20,21][22]
    5[3,4,5][11,12][16,17][18,19][20,21][22]
    6[3,4,5][13][16,17][18,19][20,21][22]
    下载: 导出CSV
  • [1] Khosla I. The scheduling problem where multiple machines compete for a common local buffer. Eur J Oper Res, 1995, 84(2): 330 doi: 10.1016/0377-2217(93)E0352-X
    [2] Huang J Z, Li A P, Liu X M, et al. Optimal design of production line layout considering buffer allocation. J Tongji Univ Nat Sci, 2015, 43(7): 1075 doi: 10.11908/j.issn.0253-374x.2015.07.018

    黄君政, 李爱平, 刘雪梅, 等. 考虑缓冲区配置的生产线布局优化设计. 同济大学学报(自然科学版), 2015, 43(7):1075 doi: 10.11908/j.issn.0253-374x.2015.07.018
    [3] Papadopoulos H T, Vidalis M I. A heuristic algorithm for the buffer allocation in unreliable unbalanced production lines. Comput Ind Eng, 2001, 41(3): 261 doi: 10.1016/S0360-8352(01)00051-1
    [4] Gupta J N D. Two-stage, hybrid flowshop scheduling problem. J Oper Res Soc, 1988, 39(4): 359 doi: 10.1057/jors.1988.63
    [5] Djellab H, Djellab K. Preemptive hybrid flowshop scheduling problem of interval orders. Eur J Oper Res, 2002, 137(1): 37 doi: 10.1016/S0377-2217(01)00094-7
    [6] Bolat A, Al-Harkan I, Al-Harbi B. Flow-shop scheduling for three serial stations with the last two duplicate. Comput Oper Res, 2005, 32(3): 647 doi: 10.1016/j.cor.2003.08.010
    [7] Guirchoun S, Martineau P, Billaut J C. Total completion time minimization in a computer system with a server and two parallel processors. Comput Oper Res, 2005, 32(3): 599 doi: 10.1016/j.cor.2003.08.007
    [8] Brah S A. A comparative analysis of due date based job sequencing rules in a flow shop with multiple processors. Prod Plan Control, 1996, 7(4): 362 doi: 10.1080/09537289608930364
    [9] Brah S A, Wheeler G E. Comparison of scheduling rules in a flow shop with multiple processors: A simulation. Simulation, 1998, 71(5): 302 doi: 10.1177/003754979807100501
    [10] Priya A, Sahana S K. Multiprocessor scheduling based on evolutionary technique for solving permutation flow shop problem. IEEE Access, 2020, 8: 53151 doi: 10.1109/ACCESS.2020.2973575
    [11] Ruiz R, Vazquez-Rodriguez J A. The hybrid flow shop scheduling problem. Eur J Oper Res, 2010, 205(1): 1 doi: 10.1016/j.ejor.2009.09.024
    [12] Khan B, Hanoun S, Johnstone M, et al. Multi-objective job shop scheduling using i-NSGA-III // 2018 Annual IEEE International Systems Conference. Vancouver, 2018: 1
    [13] Li P, Yang Y X, Du X Y, et al. Iterated local search for distributed multiple assembly no-wait flowshop scheduling // 2017 IEEE Congress on Evolutionary Computation. San Sebastian, 2017
    [14] Smutnicki C. A two-machine permutation flow shop scheduling problem with buffers. Oper-Res-Spektrum, 1998, 20(4): 229 doi: 10.1007/s002910050070
    [15] Nowicki E. The permutation flow shop with buffers: A tabu search approach. Eur J Oper Res, 1999, 116(1): 205 doi: 10.1016/S0377-2217(98)00017-4
    [16] Qian B, Wang L, Huang D X, et al. An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers. Comput Oper Res, 2009, 36(1): 209 doi: 10.1016/j.cor.2007.08.007
    [17] Wang X P, Tang L X. A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers. Comput Oper Res, 2009, 36(3): 907 doi: 10.1016/j.cor.2007.11.004
    [18] Sioud A, Gravel M, Gagne C. A genetic algorithm for solving a hybrid flexible flowshop with sequence dependent setup times // 2013 IEEE Congress on Evolutionary Computation. Cancun, 2013: 2512
    [19] Omar M K. Spreadsheet approach for solving complex flowshop scheduling problems // 2011 IEEE International Conference on Industrial Engineering and Engineering Management. Singapore, 2011: 176
    [20] Duan J H, Zhang M, Qiao G Y, et al. A genetic algorithm for permutation flowshop scheduling with total flowtime criterion // 2011 Chinese Control and Decision Conference (CCDC). Mianyang, 2011: 1514
    [21] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput, 2002, 6(2): 182 doi: 10.1109/4235.996017
    [22] Wang D J, Liu F, Jin Y C. A proactive scheduling approach to steel rolling process with stochastic machine breakdown. Nat Comput, 2019, 18(4): 679 doi: 10.1007/s11047-016-9599-5
    [23] Boufellouh R, Belkaid F. Multi-objective approach to optimize production and maintenance scheduling in flow shop environment under non-renewable resources constraints // 2019 International Conference on Advanced Electrical Engineering (ICAEE). Algiers, 2019
    [24] Wang D J, Liu F, Wang J J, et al. Integrated rescheduling and preventive maintenance for arrival of new jobs through evolutionary multi-objective optimization. Soft Comput, 2016, 20(4): 1635 doi: 10.1007/s00500-015-1615-7
    [25] Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I: solving problems with box constraints. IEEE Trans Evol Comput, 2014, 18(4): 577 doi: 10.1109/TEVC.2013.2281535
  • 加载中
图(6) / 表(2)
计量
  • 文章访问数:  873
  • HTML全文浏览量:  372
  • PDF下载量:  32
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-02-26
  • 网络出版日期:  2020-05-11

目录

    /

    返回文章
    返回