带有外包的生产调度问题文献综述.docxVIP

带有外包的车间调度问题综述孙基刚、张金龙、韩祝欣摘要：生产计划与车间的调度问题是一个相当经典和普遍存在的问题。在企业中，这一问题的解决对企业而言是相当关键的，决定了企业的产率和竞争力。有许多文献对于生产调度问题都做出了相当多的研究，但是由于竞争趋于白热化，所以外包这一外部生产力变得不可忽视，近年来对于外包调度问题的文献也不断增多。本文将基于无外包的调度问逐渐拓展至带有外包的调度问题，从模型和算法这两大角度进行综述并对可能的改进进行展望。关键词：外包；车间生产调度；算法优化；引言在一个企业的生产计划中为了按时按量的完成生产，企业的决策者就需要对生产计划进行调度，为此许多学者也得出了很多的智能算法和规则，但这仅限于理想化的生产环境。由于有关调度方面的情况多种多样。光是车间类型就有单机、并行同速机、并行异速机、并行无关联机、流水车间、柔性流水车间、加工车间和柔性加工车间。在此基础上，模型中往往还有很多其他的特定限制条件，所以，车间的调度问题相当复杂但是有具有相当高的理论价值和实际价值。由于现实中的问题往往是NP-hard的，所以现在学者们努力的方向是寻求解决问题的高效近似算法。由于现实中所存在的问题都是NP-hard的，同时现有的算法（例如：禁忌算法、模拟退火法、遗传算法、人工神经网络和拉格朗日松弛算法。）对于现实中有种种约束的问题都得不出满意解，因此，我们将通过借鉴文献中对于各种情况下的现有算法的优化算法来设计出解决自己模型的优化算法。本文主要通过在不含外包的调度问题的模型和算法的基础上，对应外包这一约束，所产生的改进模型和算法进行综述。传统生产调度问题在本文中传统的生产调度问题，就是指相对于外包调度而言不考虑外包条件的调度问题。这一类问题虽然简单且过于理想化，但是想对更为复杂的调度问题进行建模和算法设计，那这一类问题还是很有研究价值的。以下主要从模型和算法对这一问题进行阐述。常用的规则有一些问题并不需要进行算法，通过一定的规则就可以得出最优调度，在此将罗列一些常见的规则：SPT——最短加工时间优先；WSPT——加权最短加工时间优先（按/降序排列）；WDSPT——全中折扣最短加工时间优先（按降序排列）；EDD——最早工期优先（按工期升序排列）；LRPT——最长剩余加工时间最快机器优先：约翰逊法则（Johnson’s rule）[1]——在第一台机器上的加工时间短于在第二台机器上的加工时间的工件按SPT排列，反之则按LPT排列。2.2 传统生产调度的模型在传统的生产调度中，经典的模型分为确定型和随机型。所谓确定型，就是模型中的参数变量都是确定的，而随机型模型就是在确定型模型中加入了一些随机变量。在此先提及一些基本的知识，对于一个问题的描述可以用三元组α|β|γ来描述。α域描述机器环境（仅可有一项）；β域是描述加工特征和约束条件的（可没有或有多项）；γ域是目标函数。机器环境分为单机（1）、并行同速机（Pm）、并行异速机（Qm）、并行无关联机（Rm）、流水车间（Flow-shop）、柔性流水车间（FFc）、加工车间（Job-shop）和柔性加工车间（FJc）。其中单机最为基础和简单，增加数台可以执行相同工序的机器就成为了并行机，其中根据加工速度分为同速和异速，如果加工的工序不相同则是并行无关联机。流水车间可以看作是许多单机的串联，工件必须按次序经过每一台机器且无占先（preemption）。加工车间较流水车间的不同之处就是，工件不必按次序经过每一台机器也没有，且在一台机器上可有多次加工。所谓的柔性则是用并行同速机代替车间中的单机，工件可以再并列的任意一台上进行工序加工。最后也是最为随意的就是开放车间（Open-shop）在这一车间中，工件可任意加工不受限制。约束条件包括：提交时间、准备时间、中断、预先约束、故障（breakdown）、机器适用限制（）、排列（permutation）、阻塞（block）、无等待（no wait）和再循环（recycle）。对于目标函数而言，一般都是对于制造期、最大延迟加权完成时间和、折扣加权完成时间和、加权滞后和和加权滞后工作数量的最小化。确定型模型的研究成果在确定型模型中最为经典的就是单机模型，W.E.Smith(1956)[2]在他的论文中证明了WSPT对于1||是最优的。在此基础上，Rothkopf（1966a，1966b）[3]和Smith（1984）[4]分析了1||得出对于这一问题WDSPT是最优的。对于，Potts（1980）[5]给出了一个启发式算法——分枝定界法。对于并行机而言，Conway，Maxwell和Miller（1967）[6]对于SPT对的最优性做出了分析。在此基础之上，Lawler和Labetoulle（1978）[7]，Gonzalez，Lenstra和Rinnooy