购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP

3.2 生产调度问题综述

生产调度问题的研究已经发展得十分成熟,早在20世纪中期,Maxwell(1964)就已经对单机生产调度问题做了一个简单的综述,指出随着自动化程度的提高,生产设备趋向于由单个设备(通常是庞大的和复杂的)构成的系统。在许多情况下,这种单个的单元或机器并不仅仅生产单个最终产品;随着配置的改变,它还可以生产类似的但不同的最终产品。在生产各种产品时,单台机器的生产顺序会极大地影响其操作性能。该综述的目的是组织并评估该调度功能的各种方法。Graham et al.(1979)最早采取三元素法“ α | β | γ ”来描述各类车间调度模型, α 表示机器配置环境特征; β 表示一系列资源约束或者生产条件特征; γ 表示优化问题的目标函数。该三元素法在本书的2.2节已经进行了详细介绍,此处不再展开。Chen et al.(1998)对生产调度问题的复杂性、启发式算法以及近似算法进行了综述。该文章指出计算机和制造系统的调度是四十多年来学者广泛研究的课题,除了计算机和制造业之外,调度理论还可以应用于其他许多领域,包括农业、医院和交通。其研究重点是如何随着时间的推移将一个或多个资源有效地分配给多项活动。这里集中讨论确定性机器调度,假设定义问题实例的所有数据都是确定的。Koulamas(2010)对目标函数为最小化总延迟时间的单机生产调度问题做了综述。该文章回顾了单机总延误最小化的单机调度问题最新理论发展,并对其中一些问题提出了扩展。此外,还回顾了精确算法、全多项式时间近似算法、启发式算法、特殊算例等。结果表明,该问题在理论和实践上都继续吸引着大量学者的研究兴趣,当前最先进的算法能够解决多达500个作业的调度问题。Quan和Xu(2013)对单机调度问题及其求解方法进行了综述。该文章指出单机调度理论与方法的研究是一个比较困难的课题,但对于企业提高生产效率具有重要意义。单机调度问题的研究已有五十多年的历史,但其理论调度方法与实际调度问题之间仍存在一定的差距。因此,该文章综述了实际调度领域存在的问题和需要考虑的各种因素,并详细介绍了解决单机调度问题的主要方法及其应用。最后,对单机调度问题今后的研究方向和建议进行了总结。Kress et al.(2018a)对机器调度问题中的算法机制设计进行了文献综述。回顾了算法机制设计文献中机器调度设置的分类和特征问题,并扩展了Graham等人广泛接受的分类方案。

本书将对最近几年发表的有关生产调度的文献做一个简单的梳理工作,采取Graham et al.(1979)提出的三元素法“ α | β | γ ”来大概描述各个文献的研究内容。表3-1介绍了2013年以来在主流期刊发表的部分有代表性的生产调度问题相关文献。Fleszar和Hindi(2018);Chen et al.(2018);Abdeljaoued et al.(2018)研究了具有可再生资源约束的平行机调度问题,目标函数是最小化工件最大完成时间。Wang et al.(2018);Lalla-Ruiz et al.(2016);Ou et al.(2015);Xu et al.(2014)研究了当时间不充足时,允许拒绝加工某些工件的平行机调度问题,目标是最小化所有工件完成时间之和或最小化工件最大完成时间。Nesello et al.(2018);Xu et al.(2014);Zhou et al.(2014);Herr和Goel(2014);Tanaka和Araki(2013)研究了工件顺序决定的机器准备时间以及工件有交货期约束的单机生产调度问题,目标是最小化工件最大完成时间、所有工件加权完成时间之和、所有工件的加权延期时间之和或所有工件的延期时间之和。Kaplano lu(2014);Cheng et al.(2014b);Wu et al.(2013a);Liu et al.(2013)分别研究了双代理或多代理的单机生产调度问题,各代理在单机排序上存在竞争关系,目标是分别决策各个代理的最优生产顺序。Wu et al.(2013b);Shen et al.(2013);Lai和Lee(2013)等研究了工件具备退化效应或者学习效应的单机生产调度问题,目标一般为最小化工件最大完成时间、所有工件的延期时间之和等。

表3-1 有关生产调度问题的相关文献

续表 Ihka0w+l8gSENURIObKfMwYSFXORpXWOzwTLSD6Xs3WS6aQwO/AnEd5UaVfS4Z8S

点击中间区域
呼出菜单
上一章
目录
下一章
×