订单接受与调度问题求解方法与仿真研究
开篇：润墨网以专业的文秘视角，为您筛选了一篇订单接受与调度问题求解方法与仿真研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要： 在按订单生产的制造系统中，有限的生产能力与严格的订单交货期要求决策者从若干候选订单中选择接受某些订单并编制生产计划。决策者需在订单收益与拖期惩罚之间进行权衡，以所有接受订单的实际收益之和最大为目标进行优化。提出了一种禁忌搜索算法用于求解考虑日期和队列准备时间的单机环境下的订单接受与调度问题。通过计算仿真方法模拟决策过程，并与两种现有的启发式算法比较，验证了提出的解法在收敛速度以及求解效果方面有更好的表现。
关键词： 订单接受与调度； 队列准备时间； 禁忌搜索； 计算仿真
中图分类号： TP311 文献标识码： A 文章编号：2095-2163（2013）03-0033-04
Solution and Simulation for Order Acceptance and Scheduling Problem
WANG Lei， ZHAN Dechen， NIE Lanshun
（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）
Abstract： In a make-to-order production system， limited production capacity and strict order delivery date requires selection and acceptance from a set of candidate orders for production schedule. Order acceptance and scheduling decisions must trade-off to maximize total revenue. This paper presents a taboo search algorithm that solves the order acceptance and scheduling problem in the make-to-order production system on a single machine with release dates and sequence dependent setup time. Compared with two heuristics from the literature， the simulation experiment results show that the algorithm in this paper obtains near optimal solutions which are significantly better than the other two heuristics both with convergence and solution quality.
Key words： Order Acceptance and Scheduling； Sequence Dependent Setup Time； Taboo Search； Computational Simulation
0 引 言
在按订单生产（Make-To-Order， MTO）类型的制造系统中，决策者需要在有限的生产能力和严格的订单交货期两项重要约束下对多个候选订单的接受与否以及如何调度进行科学决策，确定接受其中哪些订单，并对已接订单进行生产时间安排，这类问题称为订单接受与调度问题（Order Acceptance and Scheduling， OAS）[1]。实际过程中，订单接受决策一般由企业销售和运营部门制订，这些部门希望接受更多的订单，从而带来更多的预期收益，而负责订单执行的生产部门更倾向于根据实际产能接受订单，最大程度满货期要求。于是订单接受和生产调度两阶段决策的分离即成为影响MTO型企业生产计划有效性的主要原因之一。在当今激烈的市场竞争环境下，将订单接受与生产调度进行集成决策，高效利用有限的生产资源和能力在交货期约束下圆满完成订单，力图获得更多的订单实际收益以及更高的客户满意度，这就给MTO型生产企业以及信息管理系统提出无可回避的严峻挑战。
近年来，订单接受与调度问题倍受工业界和学术界的热切关注。该类问题可视为组合优化研究领域的权衡（trade off）问题，一方面希望增加订单数量获得更多的预期收益，另一方面由于订单过多必将导致拖期而受到经济惩罚，因此需要合理安排生产资源和能力，减少订单拖期，经证明该问题属于NP-hard问题[2]。Slotnick从面向问题特点的角度对近20年来订单接受与调度问题的研究进行了系统综述与分类，主要针对单机调度、多机调度、确定型调度、随机型调度以及优化目标等五类不同的订单接受与调度问题进行分析[3]。从求解方法分析，现有研究主要分为以分支定界算法为代表的精确算法，和以各种启发式算法为代表的近似算法两类。文献[4]对一种扩展的带有拖期惩罚的单机环境订单接受问题进行了研究，提出了两种线性规划形式，并且构造了两种不同的分支定界算法，又通过仿真实验证明了对于求解订单数量小于50的测试实例则具有较好的求解效果。针对候选订单数量较多的问题实例，近似算法往往具有更好的实际应用可行性。文献[5]考虑了订单接受与调度问题中队列准备时间给计算带来的复杂性，提出了一种混合整数规划形式化模型；由于精确算法对于订单数量较大问题的求解速度表现欠佳，又提出了ISFAN和m-ATCS两种启发式方法，并在生成的较大规模测试实例上进行了仿真实验，结果表明两种启发式方法能够获得较高的收敛速度并得到可接受的解。文献[6]提出一种基于遗传算法和极值优化的混合进化算法求解生产调度问题中的订单选择与订单排序问题，通过一种组合优化模型对问题进行形式化描述，并结合遗传算法的搜索能力和极值优化算法的局部优化效率，设计了适用于该问题的混合进化算法，并通过仿真实验证明了该算法对于较大规模的订单接受与调度问题具有良好的求解质量和求解效率。
禁忌搜索（Taboo Search， TS）算法作为一种相对较为成熟的元启发式算法，已经在调度以及网络优化等多个研究领域取得了不俗的实现结果。本文针对单机环境下同时考虑日期和队列准备时间的订单接受与调度问题进行研究。首先形式化描述该问题，然后提出一种基于禁忌搜索的启发式算法求解该类组合优化问题。通过计算仿真与两种现有的启发式算法进行比较，仿真结果验证了本文提出的算法在求解质量以及运行时间方面均有优质的表现。最后总结了本文的主要贡献及未来工作方向。第3期 王磊，等：订单接受与调度问题求解方法与仿真研究 智能计算机与应用 第3卷
1 订单接受与调度问题描述
n个候选订单等待决策，记为集合N={1，2，…，n}，其中i订单的执行时间为pi，日期为ri，交货期为di，订单完工时间底线为d′i，最大预期收益为Qi，订单权重为wi，订单实际开始时间为si。单机环境下订单j与前序订单i之间的队列准备时间为setij，表示订单i结束之后，至少需要setji时间之后才能开始执行订单j。
企业通过完成订单获得收益，如果在交货期之前完成订单i则可获得最大预期收益Qi。但是，如果订单拖期获得的实际收益将随订单拖期时间Ti线性递减，每超出一个时间单元即产生一定量的拖期惩罚；如果超出底线d′i，则制造企业无法获得任何收益。本文设定订单i的权重为wi=Qi/（d′i-di）。订单i的拖期时长Ti=max{0，si+pi-di}。企业由订单i获得的实际收益即为Qi-wiTi。决策目标是从候选订单集合N中选择子集N′，N′N，使得企业通过执行集合N′中的订单而获得实际收益最大化。
采用布尔型变量yi∈{0，1}表示是否接受订单i，i∈N，如果接受订单i则yi=1，否则yi=0。布尔变量xit∈{0，1}表示所接受订单i的排序位置，其中i∈N且t∈{1，2，…，n}，如果订单i被接受且排在订单队列的位置t则xit=1，否则xit=0。基于以上定义，提出考虑时间和队列准备时间的单机环境下订单接受与调度问题的混合整数规划模型：
其中，目标函数（1）表示接受订单的实际总收益最大，Ti=max{0，si+pi-di}表示订单i的拖期时间；约束（2）表示所接受的每个订单都被安排在订单队列的一个具置，而被拒绝的订单则不在订单队列之中；约束（3）限定订单队列的每个位置至多安排一个订单；约束（4）表示订单之间的准备时间约束，即前序订单i完成并经过至少准备时间setij之后才能开始执行订单j；约束（5）表示订单必须在时间底线之前完成，否则即使完成，也不会得到任何收益；公式（6）表示变量yi，xit均为布尔变量。
本文通过设计一种基于禁忌搜索策略的启发式算法求该问题的近似最优解，并通过仿真实验检验算法的有效性。
2 禁忌搜索算法设计
禁忌搜索算法是一种模拟人工智能的元启发式算法，为了弥补一般的局部搜索算法易于陷入局部最优解的缺陷，引入禁忌表以及相应的禁忌准则来避免迂回搜索，通过设定藐视准则来赦免一些被禁忌的优良状态，算法能够保证多样化的有效搜索以最终实现全局优化。
本文提出一种基于禁忌搜索策略的启发式算法，求解上一节描述的订单接受与调度问题。禁忌搜索算法包括以下核心要素：初始解、邻域结构、禁忌表、邻域搜索策略以及藐视准则，通过设计上述算法核心要素，提出适于求解订单接受与调度问题的启发式算法。
2.1 可行解的表示
在求解订单接受与调度问题中，采用向量v=（v1，v2，…，vi，…，vn）表示解空间中的一个解，其中，vi表示订单i在订单队列中的排序位置。如果订单i被拒绝，则vi=0。例如，对于包含10个候选订单的集合N={1，2，…，10}来说，如果接受并按时间排序订单1、7、9、8、3，则该解可表示为向量v=（1，0，5，0，0，0，2，4，3，0）。这种解的表达方式同时包含了订单接受的决策结果以及订单排序的调度结果。
2.2 构造初始解
禁忌搜索算法由初始解开始迭代地寻找更优解。对于订单接受与调度问题，采用一种贪婪规则构造该问题的初始解s0，这种贪婪规则同时考虑订单收益、订单执行时间以及队列准备时间三个因素。对于订单i∈N，首先计算其收益负载率RLRi，其计算公式为：
RLRi=Qi/（pi+s′i）
（7）
其中，Qi表示订单i的最大预期收益，pi为订单执行时间，s′i=（si0+si1+…+sin）/（n+1）。
订单通过这种比例按照由高到低进行排序，从而促进能够获得更高收益的订单具有更高的优先级被接受并且排在执行队列的前面，而收益较低的订单将排在后面。同时，被拒绝订单的收益为0。一旦某个订单被拒绝，则队列中其余订单的收益负载率RLRi将要进行重新计算。
2.3 领域结构与移动操作
将禁忌搜索算法中的移动操作定义为交换和插入，并且设定当前解s*的邻域结构为N（s*）。通过交换当前解向量s*中的两个值，可以构造出相应的邻域结构。这种移动操作可以调整接受订单的决策结果以及订单排序。举例来说，当前解向量（1，0，5，0，0，0，2，4，3，0），订单执行队列为1、7、9、8、3，通过移动操作，可以得到两个邻域（5，0，1，0，0，0，2，4，3，0）以及（0，1，5，0，0，0，2，4，3，0）。第一个邻域解没有改变订单接受/拒绝的决策结果，只是调整了订单1和订单3的执行顺序；而第二个邻域解不仅调整了订单执行顺序，而且改变了订单接受/拒绝的决策结果，即拒绝订单1而接受订单2。而且，为了避免循环搜索，不允许交换解向量中两个均为0的值。不难分析，给定解的邻域结构中，解的个数不超过n（n-1）/2。
进一步分析可以得到，如果交换了两个订单的执行顺序，则整个订单集合中每个订单的完成时间、拖期惩罚以及最终实际收益都可能由于订单开始日期、队列准备时间以及交货期的影响而发生变化。如果因此造成某个订单的收益为0，则需要拒绝该订单。综上所述，通过这种移动操作以及邻域结构，可能使得决策结果中接受订单的数量减少。
2.4 禁忌表与禁忌长度
在禁忌搜索算法中，禁忌表中记录了最近的搜索步骤，通过禁忌重复搜索这些业已经过搜索的空间，避免算法陷入局部最优解或者循环中。本文设计的算法中，设定禁忌表中存储最近的n个搜索位置，在未来的搜索操作中将不再执行这些操作，除非满足特赦准则或者禁忌对象已经获得释放。比如，当前解向量为（1，0，5，0，0，0，1，4，3，0），通过交换订单1和订单3的执行顺序得到新的解向量（5，0，1，0，0，0，2，4，3，0），其中的交换操作为交换订单对（1，3）或（3，1），则将该交换订单对置于禁忌表中并在禁忌长度内不得重复交换订单1或3。
2.5 特赦准则及结束条件
本文设计的禁忌搜索算法设定的特赦准则为：如果禁忌表中的操作能够得到比当前解更优的解，则忽视该操作被禁忌的特点而得到新的当前解。而为了综合考虑问题的规模，又设定结束条件为n（n-1）/2次迭代操作。其中，n为待决策订单的数量。
2.6 禁忌搜索算法流程设计
根据以上定义的禁忌搜索算法主要元素和实施策略，构造求解订单接受与调度问题的禁忌搜索算法流程如下：
初始化禁忌表Tabulist并置空：
1.读入集合N中所有订单i的时间ri，执行时间pi，队列准备时间setij，交货期di以及订单权重wi
2. 基于贪婪规则构造生成初始解s0
3. 设定初始解为当前最好解s*s0
4. while 不满足终止条件 do
5. 构造邻域结构N（s*）
6. 在邻域中搜索优于当前解s*的更优解s′
7. if 存在更优解s′ then
8. s*s′，s′置于禁忌表TabuList中
9. else
10. 设置l=0
11. for l≤tabuLen do
12. 从N（s*）中选出相对较优解s#
13. s*s#，l++
14. end for
15. 从禁忌表Tabulist中删除s#
16. end if
17. 更新禁忌表TabuList
18. end while
3 仿真实验与结果分析
本节根据所研究问题的特点设计了仿真实验，分析所提出的禁忌搜索算法对问题求解的效果。通过与文献[5]中提出的ISFAN和m-ATCS两种启发式方法进行比较，对算法的求解质量以及收敛速度两方面给出分析结果。
3.1 测试实例
为了验证所提出的禁忌搜索算法对订单接受与调度问题的求解效果，本文首先生成了一系列测试实例。基于文献[5]提出的问题测试实例生成方法，文中根据实际问题特点对问题特征参数进行调整，并生成了更大规模的测试实例。比如，本文选择的延迟因子λ为0.1，0.5，0.9，交货期范围取值ξ分别为0.3，0.5，0.7以及0.9，针对每一组延迟因子、交货期组合，生成10个问题测试实例，因此每类问题均生成共计10×3×4=120个测试实例。同时，为了检验算法对于不同问题规模的相应效果，候选订单的数量n分别取10和100，生成了小规模、大规模两类问题实例。
3.2 仿真结果与分析
通过计算机仿真实验，本文针对候选订单数量n各自为10和100的两种小、大规模的问题测试实例，分别比较了提出的禁忌搜索算法（TS）以及文献[5]给出的ISFAN和m-ATCS两种启发式方法在求解效果、收敛速度两方面的实现性能。具体来说，针对每个测试问题，分别比较三种算法在10个实例上获得优化解的个数，以及运算时间。所有实验均在CPU主频2GHz，内存4GB的工作站执行。在问题规模n=10情况下的仿真实验结果如表1所示。
表1 n=10时m-ATCS、ISFAN和TS的性能
0.9 2 6 8 19.25 16.32 3.10
0.5 0.3 0 4 7 38.45 36.07 7.04
0.5 1 6 6 35.86 34.32 5.06
0.7 0 8 8 30.53 28.53 3.23
0.9 0 5 7 27.34 23.97 2.05
0.9 0.3 0 8 9 47.94 43.58 5.93
0.5 2 6 9 43.51 38.57 4.27
0.7 1 5 8 38.43 32.47 3.06
0.9 2 7 7 28.40 26.32 2.95
由表1所示的实验结果比较分析可知：针对候选订单数量n=10的小规模测试实例，ISFAN以及本文提出的TS算法表现较好，均能够从每组问题的10个实例中快速找到数量相近的优化解，而m-ATCS算法的求解效果相对稍差。
问题规模n=100情况下的仿真实验结果见表2。
表2 n=100时m-ATCS、ISFAN和TS的性能
Tab.2 Performance of m-ATCS， ISFAN and TS with n=100
n=10 优化解个数 计算时间
λ ξ m-AT ISF FCFS m-AT ISF FCFS
0.1 0.3 0 0 3 673.23 632.43 24.38
0.5 0 0 4 640.56 621.21 22.04
0.7 1 0 5 629.85 602.34 18.23
0.9 2 1 5 596.32 549.63 13.20
0.5 0.3 0 1 4 730.23 697.30 26.38
0.5 1 0 6 703.45 674.21 23.84
0.7 0 2 8 678.86 632.85 19.02
0.9 0 1 7 630.95 604.34 15.03
0.9 0.3 1 1 5 848.04 820.36 39.40
0.5 2 2 5 833.27 813.20 34.96
0.7 1 2 6 810.23 793.02 29.03
0.9 2 1 7 793.04 783.42 27.84
由表2所示的实验结果比较分析可得：针对候选订单数量n=100的大规模测试实例，m-ATCS和ISFAN两种启发式算法找到的优化解数量相对较少，而本文提出的TS算法仍能寻求到一定数量的优化解。还值得一提的是，TS算法的收敛性能更好，运算时间明显优越于另外两种启发式算法。
基于以上仿真实验及结果对比分析，验证了本文提出的禁忌搜索算法针对同时考虑订单日期和队列准备时间的订单接受与调度问题能够求得满意解，尤其对大规模问题，禁忌搜索算法能够更加快速地达到收敛，对于实际问题的求解将具有更好的实用价值。
4 结束语
本文针对单机环境下考虑日期和队列准备时间的订单接受与调度问题提出了一种基于禁忌搜索策略的启发式算法，将订单接受选择决策与订单排序生产计划决策集成优化，一定程度上解决了队列准备时间给问题求解带来的复杂性。通过计算仿真的方式与现有的两种启发式算法进行比较分析，验证了本文提出算法具有较好的求解效果，尤其针对规模较大的问题实例能够获得更快的收敛速度。下一步研究可以在解的鲁棒性方面进一步深入探讨，考察订单变化对于调度算法以及结果的影响。
参考文献：
[1]SLOTNICK S， MORTON T. Order acceptance with weighted tardiness [J]. Computers and Operations Research， 2007， 34（10）： 3029-3042.
[2]LAWLER E， LENSTRA J， RINNOOY K A. Recent developments in deterministic sequencing and scheduling： a survey [M]. DEMPSTER M， LENSTRA J， RINNOOY K A， editors. Deterministic and stochastic scheduling， 1982： 35–73.
[3]SLOTNICK S A. Order acceptance and scheduling： a taxonomy and review [J]. European Journal of Operational Research， 2010， 212（1）： 1-11.
[4]NOBIBON F T， LEUS R. Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment [J]. Computers & Operations Research， 2011， 38（1）： 367-378.
[5]OGUZ C， SALMAN F S， YALCIN Z B. Order acceptance and scheduling decisions in make-to-order systems [J]. International Journal of Production Economics， 2010， 125（1）： 200-211.
[6]CHEN Y， LI Y， YANG G K. Hybrid evolutionary algorithm with marriage of genetic algorithm and extremal optimization for production scheduling [J]. International Journal of Advanced Manufacturing Technology， 2008， 36（9-10）： 959-968.