单机加工问题在一般条件下的算法研究
来源:用户上传
作者:王文禹 段怡丹 陈正潇 张沐瑶
摘 要 Biskup首次将学习效应的约束条件引入排序模型，此后带有学习效应的相关排序问题受到了众多学者的关注。大量学者研究了特定条件下带有学习效应的单机排序问题，并给出了多项式算法的证明。对于更为一般条件下的此类问题，通常使用分枝定界法和启发式算法进行求解和对比验证。本文重点介绍分枝定界算法在带有学习效应的单机排序中的应用和几种常用的启发式算法，并给出了一些后续的研究方向。
关键词 排序问题 学习效应 分枝定界算法 启发式算法
中图分类号：O211.6 文献标识码：A DOI：10.16400/j.cnki.kjdkx.2020.01.022
Abstract Since Biskup firstly introduced the constraints of learning effects into the scheduling model， the related scheduling problems with learning effects has attracted the attention of many scholars. A large number of scholars have studied the single-machine scheduling problem with learning effects under certain conditions， and the proof of the polynomial algorithm is given. For the scheduling problem under more general conditions， the branch and bound method and the heuristic algorithm are usually used to solve the problem and verify by comparison. This paper focuses on the application of branch and bound algorithm in the single machine scheduling problem with learning effect， summarizes several commonly used heuristic algorithms， and gives some follow-up research directions.
Keywords scheduling problem; learning effect; branch and bound algorithm; heuristic algorithm
1 研究背景
在经典调度模型中，作业的加工时间通常被视为事先给定的常数。但是在很多实际情况下，作业的加工时间会受到加工开始时间或所在队列位置的影响而缩短，这一现象被称为“学习效应”。
带有学习效应或恶化效应的排序模型在生产调度中有着广泛的体现。同类工件的加工时间会随着机器磨合度的增加而缩短;相同程序进程的执行时间会随着计算机资源的占用而导致运行时间延长。一批相似工作的耗时会因为工人的熟练度增加而缩短，也会因为疲劳程度的增加而延长。
自Biskup[1]首次将学习效应这一约束条件引入排序模型以来，带有学习效应的排序问题受到了众多学者的关注和研究。對于一些具有准备时间、截止日期、群组调度等不同条件下的单机排序问题，文献[2-9]等给出了特定情形最优解的多项式算法。对于未被证明是多项式问题的具有更一般条件的排序问题，文献[10-12]使用分枝定界的方法寻找问题的全局最优解，提出启发式算法快速求出局部最优解，并对比与局部最优解的误差进行检验。
本文重点介绍分枝定界算法在带有学习效应的单机排序问题中的应用，总结了几种常用的启发式算法，并给出一些后续的研究方向。
2 分枝定界算法
排序问题是一类组合最优化问题。对于具有一般条件的学习效应单机排序问题，其计算的复杂性无法得到解决。已有研究通常使用分枝定界的方法寻找问题的全局最优解，这类算法在解决小规模问题时具有良好的表现。
在极小化目标函数的排序问题研究中，分枝定界法通常包含遍历搜索、下界和优势性质三个部分。
2.1遍历搜索
单机排序问题的分支定界法中，每一个节点对应一种完整的排序，以节点所在层数为界分为前后两部分。前半段的作业排序确定，后半段的作业排序处于未知状态。对于作业总数为n的排序问题，以1个全部排序未知的节点为根节点，个全部排序已知的节点为第n层叶节点，组成排序问题的搜索树。
节点的搜索有广度优先搜索（BFS） 和深度优先搜索（DFS）两种搜索算法。应用在排序问题当中，两种算法以不同的方式从顶到下遍历整颗搜索树以找到全局最优解。由于计算机实现方式的差异，两者具有各自的优缺点。
BFS每次访问所有已知节点中的最优节点，直到找到全局最优解。通过保存所有搜索过的节点信息，以减小重复访问的计算量。优点是搜索速度较快，缺点是会占用大量内存。DFS访问时只从当前节点的后续节点中选择最优节点，找到可行解后向上回溯，不会重复进入已经搜索过的节点。优点是占用内存很小，缺点是速度相对较慢。
通过对排序算法的数值仿真可以发现，BFS在处理规模较大的问题时会出现内存不足的问题，DFS则可以通过延长运行时间来保证得到全局最优或较好的局部最优解。在目前的研究中，DFS是数值仿真时常用的搜索方法。 2.2下界
下界是分枝定界算法主要的剪枝方式，其好坏程度极大的影响着分枝定界算法的效率。节点的下界与该节点的最佳值误差很大时，分枝定界几乎等同于穷举;而良好的下界可以在计算时快速的进行大量剪枝，使算法在面对较大规模问题时依旧十分有效。
下界的好坏主要取决于节点下界计算结果和节点最佳值的接近程度，其次是计算过程的时间复杂度。
下界表达式的推导存在多种理论依据，参考部分文献的研究过程，有以下两种较为普遍的方式：
（1）对于具有一般性的原排序问题模型，通过取极值或特定值等方式统一部分参数，使得新问题的最优解不大于原问题的最优解，即找到原问题在更好情况下的一个特例问题（convex那篇）。若新问题是多项式可解的，例如化为指派问题，即可计算出原问题的一个下界。
（2）每个作业的开始时间受到作业准备时间和上一作业完工时间两项约束。因此，如果只单独考虑其中一项约束，将原目标函数缩小，此时新目标函数的最小值必定小于原问题的最优解。当新的目标函数使用SPT等启发式算法可以求得最优解时，可以较为容易的得到原问题的一个下界。
2.3优势性质
优势性质是分枝定界法的另一个剪枝方式。假设有两个作业加工排序A和B，其中只有两个加工次序相邻的作业顺序不同。当作业属性、排序顺序参数满足一定条件时，排序A必定优于排序B。例如，一个作业如果准备时间较大且处于最先加工的位置，可以考虑先加工其他作业而不影响该作业的开工时间。
使用多条优势性质对搜索树进行剪枝，在下界计算的时间复杂度较高时，可以有效的加快最优解的求解速度。
3 启发式算法
已有的文献和经验表明，对于一些简单的单机排序问题，存在一些对应的启发式规则用于最优解的计算。这些启发式规则通常是根据全部作业某些属性的数据进行排序以得到最优序列。后续的大量研究证明，很多其他特殊情形的排序问题，同样可以使用已有的启发式规则得到最优解。
对于一般条件的排序问题，使用多种启发式规则得到一个较好的初始解序列，然后使用多项式时间的贪心算法进行遍历搜索，可以在绝大多数情况下得到一个误差较小的局部最优解。下面给出了几种常用的启发式规则。
3.1 WSPT
加权最短加工时间优先（weighted shortest processing time first，简记WSPT）规则。该规则按照 /非增的顺序对所有任务进行排序。
3.2 SPT
最短加工时间优先（shortest processing time first，简记SPT）规则。SPT规则按照非减的顺序对任务进行排序，是WSPT规则在相同时的特殊情形。
3.3 EDD
最早工期优先 （earliest due date first，简记EDD）规则。EDD规则按非减的顺序对任务进行排序。
3.4 ECT
最早完工时间优先（earliest completion time first）规则。每当处理机空闲时，在尚未排序且已经到达的任务中，选取最早完工时间最小的任务加工。如果有多个任务的最早完工时间相同且最小，则选取最早开工时间最小的任务。
3.5 EST
最早开始时间优先 （earliest start time first） 规则。当处理机空闲时，在后续任务中选取最早开始时间最小的任务加工。如果有多个，则选取完工时间最小的任务。
3.6针对特定问题的其他规则
除了具有代表性的启发式算法外，一些文献针对特定的问题，以作业参数的某种函数值作为基准，提出了新的启发式规则。相比于基础的启发式规则，适合自身目标函数的启发式规则通常在寻求初始解时有更好的表现。
4 总结
本文对于带有学习效应的单机排序问题的文献进行了研究和总结，介绍了针对一般条件下的两种求解算法。其中，分枝定界法用于求出全局最优解，面对大规模问题时会花费难以允许的时间。启发式算法可以在极短时间内得到一个误差未知的局部最优解。其中，分枝定界的下界和启发式算法的初始解都由多项式算法决定。因此，本文认为存在以下三个研究方向。第一，对于广泛的排序问题，寻找多项式时间的求解算法依然重要。多项式问题数量的增加可以为分枝定界法的下界的计算表达式提供更多的方向选择和理论依据，减小节点下界和节点最优值的百分差，提高分枝定界法的剪枝效率。第二，對于一般条件的学习效应单机排序问题，基于已解决的多项式问题和当前问题的特殊性质，寻求和准确值差值更小的下界计算表达式，以增加一定时间内的可以解决的问题的规模。第三，对于一般条件的排序问题，可以寻求误差更小的启发式规则计算初始解。若得到的局部最优解的误差在允许范围之内，启发式算法和分枝定界等算法相比将在运行时间上具有巨大的优势。
参考文献
[1] Biskup D. Single‐machine scheduling with learning considerations[J]. European Journal of Operational Research，1999.115（1）：173-178.
[2] 王吉波. 工件加工时间可变的现代排序问题[D].大连理工大学，2005.
[3] 陶明子，赵传立.具有安装时间和学习效应的单机排序问题[J].运筹与管理，2010.19（04）：101-107.
[4] 胡晨晨. 带有学习及退化效应的排序问题[D].沈阳师范大学，2015.
[5] 白静，刘璐，王吉波.具有截断学习效应和工件带准备时间的单机排序问题[J].运筹与管理，2014.23（06）：152-156.
[6] 王利岩.工件具有学习与恶化效应的现代排序问题研究[D].大连理工大学，2014.
[7] 刘洋.具有学习效应和退化效应的单机排序问题[D].沈阳师范大学，2011.
[8] 陶明子，赵传立.具有学习效应和非线性安装时间的单机排序问题[J].沈阳师范大学学报（自然科学版），2010.28（01）：8-11.
[9] 胡晨晨，赵玉芳.同时带有安装时间和送出时间的单机排序问题[J].沈阳师范大学学报（自然科学版），2015.33（03）：351-357.
[10] 赵传立.具有学习效应的排序问题的某些新进展[J].沈阳师范大学学报（自然科学版），2014.32（4）：453-460. DOI：10.3969/j.issn.1673-5862.2014.04.001.
[11] 王吉波，刘璐.带准备时间的任务单机学习效应排序问题[J].大连理工大学学报，2013，53（06）：930-936.
[12] 闫萍，王吉波，赵礼强.带准备时间的单机指数时间学习效应排序问题[J].运筹与管理，2017.26（11）：70-76.
转载注明来源:https://www.xzbu.com/8/view-15172836.htm
