作者：虞先玉,张玉林,汪操
出版社：清华大学出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
时间可变的运作调度模型与算法试读：
前言
随着信息技术的飞速发展，顾客对产品生产与配送的时效性要求也越来越高，未及时送达顾客的产品往往导致顾客索赔或商家信誉受损。为了应对产品生产与配送时效的需求，厂商会根据获得的生产与配送运作信息，制定产品生产与配送的最优调度顺序。由于受工作人员及机器等的学习效应／老化效应影响，产品在实际生产或配送中的处理时间往往会随其所在调度处理的序列位置变化而变化，这种变化显然会影响厂商的产品运作调度的效益与效率。考虑产品生产与配送任务处理时间可变性的调度研究近年才刚刚兴起，系统分析产品处理时间可变影响下考虑机器维护、两个代理、产品分组、处理时间上限约束、拒绝惩罚等相关调度研究尚有很多创新工作需要推进和深入。为此，本书在产品处理时间可变影响情形下针对产品生产与配送调度过程中的系列调度问题进行研究，建立相应的调度模型，设计求得最优或近似调度方案的求解算法。
全书共分为9章，主要内容概括如下：第1章为绪论，简要介绍本书调度研究的研究背景以及相关问题研究现状；第2~7章分别结合机器维护、两个代理、产品分组、处理时间上限约束、拒绝惩罚等因素对生产调度问题的近似算法和最优算法进行分析研究，并分析算法的计算复杂度；第8~9章分别研究单顾客和多顾客情形下的生产与配送集成调度问题，并分别给出了多项式最优算法和多层编码的进化算法求解问题。
本书的撰写和出版得到了南京航空航天大学经济与管理学院、东南大学经济管理学院领导和老师的关心和支持，也先后得到了国家自然科学基金（71671036）、中央高校基本科研业务费专项资金（NS2016080、NR2016005）和国家博士后基金（164117）的支持和资助。感谢加拿大麦克马斯特大学乔治·斯坦纳教授、黄楷老师和张睿博士在本书的相关研究过程中给予的指导和支持，也感谢同学、朋友和同事及科研合作者徐德华博士、殷允强博士对本书研究提出的宝贵建议。非常感谢彭芳、李杰澔两位同学在本书部分内容修改和校对过程中付出的辛勤工作。感谢清华大学出版社责任编辑为本书所做的大量工作。
由于作者的水平有限，书中难免有错误和不妥之处，欢迎读者批评指正。作 者2016年9月第1章绪论1.1运作调度的产生和发展
在飞机降落跑道的选择、制造企业生产机器和任务的安排、授课教室的排定等很多实际活动中，都包含着对资源和任务的运作调度过程。运作调度是把限量的资源分配给一定数量的任务并优化给定调度目标的活动。
早期的运作调度研究可以追溯到20世纪50年代发表在国际期刊Naval Research Logistics Quarterly上的调度论文。在20世纪60年代，随着线性规划和动态规划理论的发展，规划模型构建以及精确求解方法设计逐渐成为运作调度研究的热点。到了20世纪70年代，随着计算复杂性理论的发展，调度问题的计算复杂度研究得到了长足的发展。在20世纪末，一些新的调度研究方向，如随机调度、不确定性调度、在线调度、分组调度等受到了广大学者们的关注。在1998年，国际专业期刊Journal of Scheduling正式出版，标志着调度理论及其应用研究进入了新的发展时期。1.1.1 研究背景
生产车间中产品的生产、物流公司货物送达时间的安排、建筑项目的施工、学校教室的安排等日常生活中普遍存在的问题，实际上都属于在给定时间内将稀缺资源依序在任务序列中分配的生产调度决策问题。
在当今经济全球化和信息技术飞速发展的背景下，从企业产品生产到产品交付顾客的时间间隔不断缩短，顾客对产品的生产与配送运作调度的时效性要求越来越高。进入21世纪，我国经济持续发展，已经成为“世界工厂”，但我国产品制造和物流的成本长期偏高。我国制造业经过多年的发展仍然没有完全走出“高消耗、低收益”的处境。
据2014年中国物流与采购联合会的检测资料显示，我国物流费用占国内生产总值比例不仅比美国和日本等发达国家高出1倍以上，还高于巴西等发展中国家。我国制造企业和物流运输企业迫切需要降低产品制造和物流运输过程中的运作成本，实现的途径之一是优化产品生产与配送过程中的运作调度。
在很多实际的产品生产或配送的事例中，产品生产与配送所需的实际时间往往因为工具的老化、工人技术积累等因素改变而变化（如Alidaee和Womer(1999)）。例如，随着快递业新入职员工对配送区域的路径、交通、顾客等信息的逐渐熟悉，配送时间逐渐减少，配送效率将不断提高。这类随着新的生产知识和技术的学习，完成任务的效率逐渐提高，偏后安排的任务的处理时间相对较短的现象，在调度研究中也称为学习影响（如Biskup(1999)）。又如，在钢铁厂的轧钢车间，随着轧刀不断地切割钢材，轧刀会逐渐变钝，切割同型号钢材所需时间也会逐渐变长。这种由于精力与体力等限制，在连续任务时间过长、任务强度过大、对掌握的知识与技术遗忘、生产与配送过程中机器的磨损老化等而带来的偏后安排的产品的生产和配送处理时间变长的现象，在调度研究中也称为老化影响（如Cheng等（2004）、Gawiejnowicz(2008)）。
更一般的情形是，工人生产知识积累和生产机器老化同时存在于产品生产与配送过程中，学习影响和老化影响同时发生作用。此时，偏后安排的任务所对应的处理时间可能变长也可能变短，本书统称之为处理时间可变影响。老化影响和学习影响都是时间可变影响的特殊情形。
自20世纪初期Henry Gantt等先驱推动的传统调度研究起，虽然取得了较丰富的成果并在制造业中广泛应用，但已有的多数成果均假设任务处理时间在任务处理过程中保持不变（如Graham等(1979)、Pinedo(2002)），这与管理日益精细化的现实要求有明显差距。今天，要做好产品生产与配送的调度，必须要考虑处理时间可变影响，需要对这种处理时间可变影响下的生产与配送进行深入研究。1.1.2 研究意义
毫无疑问，产品的实际生产时间或配送时间随着调度位置的不同而变化必然会影响产品生产与配送的调度决策，也会影响所有产品生产与配送任务的完成时间。而传统的调度决策的一个基本假设是，产品生产与配送时间在运作过程中固定不变，由此得到的调度决策方案很多时候只是近似的优化调度方案，在某些情形下甚至都不能执行。为了满足顾客对于产品生产与配送时效性日益严格的要求，今天的产品生产与配送调度日益需要重视这种处理时间的可变性，需要对此进行深入研究。（1）在理论意义上，考虑处理时间可变的产品生产与配送的调度研究将丰富调度理论研究。调度研究最早兴起于第二次世界大战中军工资源的运作管理，随后迅速发展到其他领域。早期的调度研究假设任务处理时间在资源调度过程中是不变的，没有考虑处理时间可变影响。近年来，诸多研究虽然考虑了老化影响和学习影响，但较少针对更有实用价值的时间可变影响展开研究，同时考虑时间可变影响、机器维护和分组调度技术的研究则更少。（2）在实际运用中，考虑处理时间可变的产品生产与配送的调度研究成果能为厂商的生产与配送调度提供支撑。信息化技术和现代化物流技术得到了广泛应用，为时间可变的调度理论研究和实际调度运作之间信息交互与结合提供了实际技术基础。相比于传统的处理时间不变的假设，研究处理时间变化情形下的生产与配送调度更接近实际。基于处理时间可变性假设的生产与配送的调度决策也相应地更能有效地促进实际过程中的产品生产与配送任务的高效处理，更好地满足顾客订单时效性的要求，可以为实际的产品生产与配送调度提供技术支持和决策参考。
综上所述，随着我国经济的快速发展，迫切需要提高产品生产与配送的效率，从而降低相应的机会成本和运作成本。而处理时间可变影响在产品生产与配送过程中普遍存在，因而，深入研究处理时间可变影响下的产品生产与配送调度，具有较重要的理论价值和较大的实践价值。1.2时间可变的运作调度1.2.1 处理时间可变影响的函数形式
针对任务完成过程中的实际加工时间如何变化以体现老化／学习效应，学者们提出了种种能描述这类处理时间可变的具体函数形式，并探讨了优化调度方案的确定方法。本小节将分别从处理时间函数为线性、指数、线性与指数的结合、一般复合形式，以及其他形式进行概述。1．处理时间可变影响为线性函数形式
Mosheiov(1991)首先针对任务处理时间随着机器老化和工作人员疲劳逐渐变长的老化影响，构建了反映这种老化影响的线性函数形式的模型，并给出了能确定单机调度方案的V型排序算法。继该研究之后，关于老化／学习影响加工处理时间为线性函数形式的研究成果迅速增多。
针对任务实际处理时间与加工完成的任务数量正相关的老化影响，Cheng和Wang(2000a)建立了描述这种老化影响的处理时间线性函数模型，在最小化任务完成时间延迟的成本要求下，证明了该问题的NP难性，设计了求得近似最优调度方案的启发式近似算法。Bachman和Janiak(2004)提出了与已完成任务数量相关的处理时间函数模型，即任务的实际处理时间为任务基本处理时间和任务所在排序位置的线性函数模型，并基于该模型在最小化任务处理时间表长、最小化总完工时间及最小化总加权完工时间等成本要求下，分别给出了求得近似最优调度方案的最短任务准备时间优先算法，且讨论了这些优化算法的最坏情况比。
不同于使用处理完成的任务数量的线性函数形式来表示任务实际处理时间，还有一些学者用任务开始处理时间的线性函数形式来表示任务实际处理时间。如，赵传立等（2003）在任务实际处理时间是任务开始处理时间的线性函数模型下，分别提出了最小化任务处理时间表长、最小化总加权完工时间及最小化总延迟等成本要求的确定最优调度方案多项式时间算法。类似于赵传立等（2003）的研究，Wang和Xia(2006)分别在最小化任务处理时间表长和最小化总完工时间的目标要求下，得到了确定最优流水车间调度方案的多项式时间算法。刘鹏等（2011）在赵传立等（2003）的任务处理时间模型基础上做了改进，将任务的实际加工时间表示为任务基本加工时间和任务开始加工时间的递减线性函数之积，在一个代理目标不超过给定上限、另一个代理的任务处理时间表长及最大延迟最小化的目标要求下，得到了求得最优调度方案的多项式时间算法。
还有一些其他描述时间可变影响的线性函数模型及相应研究。如，针对旧产品恢复再制造的生产调度，Inderfurth等（2006）提出描述产品的实际再制造时间随着处理时间增长而逐渐递增的线性老化函数形式，建立制造与再制造的两阶段线性规划模型，提出求得近似最优调度方案的多项式动态规划算法。Rudek(2014)针对任务实际处理时间同已经完工的任务处理时间总和之间存在正相关的情形，提出任务的实际处理时间是已处理完成的任务时间总和的线性函数模型，针对最小化总完工时间的成本目标，提出启发式算法求解优化调度方案。2．处理时间可变影响为指数函数形式
不同于上述处理时间可变影响为线性函数的模型，不少学者认为可变影响在一段时期内呈现指数函数模型形式的加速效果。Mosheiov(2001)认为学习影响下任务处理效率在一段时期内是加速提高的，从而提出任务的实际加工时间表示为任务基本加工时间和排序位置的指数函数之积的指数函数形式的模型，并给出单机调度、平行机调度相应最优调度方案的改进任务指派的多项式算法。考虑到实际生产运作中重复循环的老化影响，Kuo和Yang(2008)建立了两类使用任务基本处理时间和任务所在位置的指数函数之积描述的处理时间可变影响模型，在最小化处理时间表长的目标要求下，给出了确定单机最优调度方案的多项式求解算法。类似于Kuo和Yang(2008)，一些文献（如Biskup(2008)、Yang等(2010)、Yang和Yang(2010)、Zhao和Tang(2010)）在任务处理时间是任务基本处理时间和任务所在位置的指数函数之积的函数模型下，设计了确定优化调度方案的多项式算法。在学习影响为指数函数形式情形下，Lee和Chung(2013)提出了任务数量为中等规模、目标为最小化总延误的确定流水车间最优调度方案的分支定界求解方法；对任务数较大规模情形，给出了两个确定近似最优调度方案的启发式算法。3．处理时间可变影响为指数函数与线性函数结合形式
一些学者提出了时间可变影响为线性函数和指数函数构成的复合形式模型。Lee(2004)较早地使用了线性函数和指数函数混合形式的任务实际处理时间可变影响模型，即任务的实际处理时间等于任务开始加工时间的线性函数和任务排序位置的指数函数的乘积，分别给出了在最小化任务处理时间表长和最小化总流水处理时间的目标要求下求得最优调度方案的多项式时间算法。Cheng等（2008）运用已完成任务基本处理时间线性函数以及任务排序位置的指数函数的结合形式，建立了任务处理时间可变影响模型，在最小化任务处理时间表长和最小化总完工时间的目标要求下，分别设计了求解最优单机调度方案的多项式算法；在最小化任务处理时间表长和最小化总完工时间的目标要求下，分别给出了求得特殊情形下的最优平行机调度方案的多项式算法。在线性函数和指数函数混合形式的时间可变影响下，Hsu等（2013）把每项任务实际处理时间表示为次幂随任务改变而变化的指数函数形式，把机器维护时间表示为维护开始时间的线性函数形式，在最小化机器总负荷等成本要求下分别给出了求得最优非关联平行机调度方案的多项式时间算法。类似于Lee(2004)和Hsu等（2013），一些文献（Wang(2007)、Wang和Cheng(2007)、Cheng和Lee(2010)、Yang和Yang(2010)、郭鹏等（2011）、和Gawiejnowicz(2013)）也使用了线性函数与指数函数结合形式的任务处理时间可变影响模型，基于给出的处理时间可变影响模型分析任务调度方案性质，给出了求得任务调度方案的多项式最优算法及近似算法。4．处理时间可变影响为一般性函数形式
不同于线性、指数、线性与指数复合的任务处理时间可变影响的函数模型，一些近期的调度研究文献关注了不包含具体线性函数形式或指数函数形式的一般性任务处理时间函数模型。Yin等（2009）提出了任务处理时间学习影响的一般性函数模型，即任务实际处理时间等于任务基本处理时间、已处理任务基本时间的一般性复合函数与任务排序位置的一般性函数的乘积，并证明了所考虑的单机任务调度仍然是多项式时间最优可解的。随后，Lai和Lee(2011)对文献Yin等（2009）中的任务处理时间函数模型进行了改进，得到了新的任务处理时间函数模型，即任务实际处理时间等于任务基本时间及已处理任务基本时间和的一般函数与任务排序位置一般函数的乘积形式，在最小化任务总加权完工时间、最小化最大延迟以及最小化总延误等目标要求下，分别给出了求得最优单机调度的多项式时间算法。Wang和Wang(2013)建立了通过已处理任务准备时间和任务排序位置的一般性复合函数表示的任务处理时间学习影响模型，在最小化单机任务处理时间表长、最小化总加权任务完工时间以及最小化流水处理总延迟的成本目标下，分别给出了多项式时间算法求得最优单机调度方案以及最优流水车间调度方案。Yu等（2013）利用Wang和Wang(2013)提出的学习影响的函数形式研究了老化影响下的流水车间调度，并证明了可以通过最大任务处理时间优先（LPT）规则得到最优的流水调度方案。Shen和Wu(2013)建立了通过处理任务已消耗时间、任务排序位置及任务开始时间的一般性复合函数表示的任务处理时间函数模型，得到了在最小化任务处理时间表长要求下求得最优单机调度方案的多项式时间算法。这些研究成果（Yin等(2009)、Ng等（2010）、Lai和Lee(2011)、Wang和Wang(2013)、Yu等(2013)、Shen和Wu(2013)）的任务实际处理时间函数模型仍然包含有任务处理时间的相加及相乘等具体的运算过程。
一些文献进一步考虑了不包含具体函数运算结构的任务处理时间可变影响的函数模型。Mosheiov和Sidney(2003)提出了不含任何特殊运算结构和特殊函数结构的一般性任务处理时间函数模型，即所有任务实际处理时间通过任务基本处理时间和排序位置的共同的一般性复合函数表示，并在最小化单机任务处理时间表长、最小化单机总流水时间以及最小化平行机总流水时间等目标的要求下，分别给出了确定相应最优调度方案的多项式时间算法。Yu和Fan(2010)推广了Mosheiov和Sidney(2003)的任务处理时间函数模型，把各项任务的实际处理时间通过任务基本处理时间和排序位置的各自不同的一般性复合函数表示，并分析得到求得最优的单机调度方案的多项式时间算法。基于Mosheiov和Sidney(2003)给出的一般性位置依赖的任务处理时间模型，Mosheiov(2011)研究了以最小化流水处理时间为优化目标的流水车间调度，给出了求得最优流水车间调度方案的多项式时间算法；Mosheiov(2012)研究了以最小化机器总负荷为优化目标的平行机调度，并分别给出了求得最优平行机调度方案的多项式时间算法。Yu等(2014)进一步研究了Mosheiov(2012)的平行机调度问题，得到了求得最优平行机调度方案的更高效的多项式时间算法。5．描述处理时间可变的其他形式
除了以上描述处理时间可变影响的线性、指数、指数与线性结合、一般初等函数形式，也有一些文献采用其他形式描述了任务处理时间可变影响。Rustogi和Strusevich(2012b)采用任务时间、任务位置的不等式组表述处理时间可变影响，在最小化任务的处理时间表长的目标要求下，给出了多项式时间算法求得最优的平行机调度方案。Rudek和Rudek(2013)采用文献Rustogi和Strusevich(2012b)类似的方法描述任务时间可变影响，通过一组任务实际处理时间的不等式约束条件来描述任务处理时间可变影响，在最小化处理时间表长的目标要求下，得到求得最优流水车间调度方案的多项式时间算法及其计算复杂度。Rudek(2014)建立了通过任务基本处理时间、任务排序位置的分段函数表示的任务实际处理时间模型，在最小化总加权完工时间的要求下，基于动态规划方法给出了求得最优调度方案的伪多项式算法。Yeh等(2014)运用模糊数表述任务实际处理时间影响，在最小化处理时间表长的成本要求下，给出启发式算法求得近似最优的平行机调度方案。1.2.2 考虑机器维护的生产调度
产品生产或配送过程中，生产机器或配送车辆的累积使用会导致生产机器磨损或配送车辆老化，这会增加当前任务及后续任务的处理时间，带来成本的增加。克服这种老化效应的方法是加工处理过程中适时进行机器维护，提高机器服务的能力。Palmer(1999)及Nyman和Levitt(2010)认为好预防性维护操作可以减少老化效应带来的损失；机器维护事关资源的优化调度，是重要的运作调度技术（Gopalakrishnan等，1997）。本小节将分别从单机器和多机器两个方面对相关研究成果进行综述。1．单机器调度
一些文献关注了考虑一次机器维护或一次机器不可使用的时间区间的单机调度研究。Mosheiov和Oron(2006)研究了在最小化工期延误的目标要求下包含一次机器维护的单机调度，并给出了求得最优调度方案的多项式时间算法。Gordon和Tarasevich(2009)针对Mosheiov和Oron(2006)的单机调度问题提出了求得最优调度方案的新求解算法，新求解算法的计算复杂度比Mosheiov和Oron(2006)给出的求解算法计算复杂度更低。Breit(2006)研究了不可中断任务组在一个给定的时间区间里机器不可用的单机器调度问题，提出了求得近似最优的调度方案的近似算法，并通过数值算例验证了该算法可以在合理时间得到最坏情况界较小的可行解。与Breit(2006)的研究问题相似，Kacem(2007)研究了任务处理过程不可恢复且机器有一个不可用时间区间的单机调度，给出了求得可行的调度方案的近似比为2的多项式近似算法。马英等(2007)针对在一段给定时间内机器不可用情况，研究了部分任务处理过程可恢复的单机调度，在最小化任务处理时间表长的要求下，基于LPT规则提出了一个求得近似最优调度方案的启发式算法；在最小化加权完成时间之和的成本要求下，给出了求得最优调度方案的动态规划算法。
考虑到实际任务运作处理过程中机器可能需要进行多次维护，一些文献研究了包含多次机器维护或不可用时间段的单机调度。Gawiejnowicz(2007)研究了考虑任务处理独立、不可中断和比例老化的单机器调度，机器不可用的时间段的数量、开始时间和结束时间是给定的，在最小化任务完工时间的要求下，给出了多项式时间近似算法求得可行的调度方案。针对生产机器的固定周期机器维护，Liao和Chen(2003)在最小化任务总延迟时间的要求下，给出了求得满意单机调度方案的启发式算法。在最小化任务处理时间表长的成本要求下，Ji等(2007)把相邻的两次机器周期维护间的时间间隔看做是放置任务的箱子，运用经典的装箱问题的研究结论来分析得到LPT算法求解机器周期维护的单机调度的最坏情况比为2，并指出从最坏情况比的角度LPT算法是最优的多项式时间近似算法之一。Yu等(2012)从启发式近似算法的角度研究了Ji等(2007)中的机器周期维护的单机调度，给出了求得近似最优调度方案的混合遗传算法，并通过算例验证了所给出的混合遗传算法能够在合理的时间内求解得到满意的调度方案。针对考虑任务不可恢复和机器维护时间可调的单机调度问题（SJM），Chen(2008)给出了在最小化任务处理时间表长的成本要求下求得近似最优调度方案的启发式算法，并指出Ji等（2007）所研究的机器周期维护的单机调度问题是SJM问题的特殊情形。Xu等（2009）认为，Chen(2008)提出的近似算法和经典的LPT算法等价，求解SJM问题的最坏情况比为2；从最坏情况比的角度看，Chen(2008)提出的算法是求解SJM问题的最优多项式近似算法之一。Xu和Yin(2011)证明了Graham(1966)提出的LS算法求解在线情形的SJM问题的最坏情况比为2。Xu和Yin(2011)研究指出，从最坏情况比的角度分析，同LPT算法一样，LS算法也是求解机器周期维护的单机调度问题以及SJM问题的最优近似算法。Yu等(2013a)研究了考虑两个任务代理和机器计件维护的单机调度，在目标函数为任务完工时刻的整系数多项式函数的条件下，给出了求得最优调度方案的多项式时间算法。
不同于以上任务处理时间给定的机器维护调度研究，一些近期的文献关注了同时包含线性函数形式或指数函数形式的任务处理时间可变影响和机器维护操作的单机调度研究。Mosheiov和Sarig(2009)研究了包含一次机器维护的处理时间可变影响的单机调度，即把任务的处理时间表示成机器维护时间的线性函数，在最小化任务延误、任务早熟及时间窗安排的总代价的要求下，给出了求解最优的单机调度方案多项式时间算法。针对机器带有一个不可用时间段的单机调度问题，马英等(2010)建立了线性函数形式的任务处理时间老化影响模型，在最小化任务处理时间表长的要求下，动态规划算法可以求得最优调度方案，而通过计算复杂度较低的启发式算法可以得到近似最优的调度方案。蒋志高和董明（2011）建立了指数函数形式的任务处理时间学习影响模型，研究了包含多阶段时间窗（time-window）周期维护的单机调度，在最小化任务处理时间表长的要求下，提出了求得可行调度方案的多项式近似算法。Mosheiov和Sidney(2010)给出了线性函数形式的机器维护时间可变影响模型，在最小化任务处理时间表长、最小化任务总完工时间及最小化任务最大延误时间等成本要求下，分别给出了求得最优调度方案的多项式时间算法。类似地，文献（Gordon和Strusevich，2009；Lodree和Geiger，2010）也分别运用了线性函数形式和指数函数形式的任务处理时间可变影响模型，并基于给出的处理时间可变的函数模型，分别给出了求得单机调度方案的多项式时间算法。
不同于指数函数形式和线性函数形式的时间可变影响，一些文献也研究了采用其他形式表示任务处理时间可变影响的包含机器维护的单机调度问题。Rustogi和Strusevich(2012a)通过约束不等式组表述任务处理时间的老化影响，研究了老化影响下机器维护的单机调度问题，给出了求得在最小化任务处理时间要求下的最优调度方案的多项式时间算法。Yu等（2012a）研究了机器计件维护的单机调度，把机器维护时间表述为相邻两次维护之间完成的任务处理时间总和的线性函数，在最小化总调度成本的目标要求下，给出了求得单机最优调度方案的多项式时间算法。Yu和Zhang(2014)采用任务排序位置的一般性函数形式表述任务处理时间可变影响，研究了同时包含机器维护和任务处理时间上限约束的单机器调度，在最小化完工时间的成本要求下，证明得到可以使用多项式时间的匈牙利算法求得最优调度方案。Xue等（2014）通过分段函数表示区间约束的任务处理时间可变影响，在最小化任务完工时间及区间约束超出惩罚表述的总调度代价的目标要求下，得到了计件维护下的确定单机最优调度方案的多项式时间算法。2．多机器调度
一些文献研究了包含机器维护的多机器调度。针对每台机器上均有一段不可使用时间的双机流水车间调度，Cheng等（1999）提出了求得满意任务调度方案的启发式算法。随后，对两参机器中只有一台机器有一段不可使用时段的双机器流水车间调度，Cheng和Wang(2000b)提出了能求得近似最优调度方案且最坏偏误界更小的改进启发式算法。Vahedi-Nouri等（2013）采用任务基本处理时间及排序位置指数函数的乘积表述任务处理时间学习影响，研究包含一个机器可用性约束的多机器流水车间调度，在最小化任务总流水处理时间的要求下，分析得到最优调度方案的多项式时间算法。1.2.3 考虑分组技术的生产调度
实践中经常将相似特征的任务分在同一组加工，同组中不同任务之间机器不需要准备操作，其实质就是考虑任务分组的调度。Ham等（1985）将任务按相似特征分组处理称为分组技术。本小节将分别从处理时间函数为线性、指数、一般形式对相关分组调度研究成果进行综述。1．处理时间可变影响为线性函数形式的分组调度
近年来，一些学者同时考虑了任务分组技术和线性函数形式的任务处理时间可变影响。Wu等（2008）研究了任务处理时间可变的单机器分组调度，把分组发动时间通过任务开始处理时间的线性函数表述，分别在最小化处理时间表长和最小化总完工时间的成本要求下，给出求得最优调度方案的多项式时间算法并分析了算法的计算复杂度。闫杨等（2009）研究了同时包含老化影响和学习影响的单机器分组调度，分别在最小化处理时间和最小化总代价的目标要求下，给出了最优调度方案的多项式时间求解算法。Liu等（2010）基于线性函数形式的分组发动时间模型以及线性函数形式的任务处理时间模型，研究最小化第一个代理总完工时间且用给定上限约束第二个代理总代价的单机分组调度，分析得到多项式时间算法求得最优的单机调度方案。Wang和Sun(2010)通过任务开始时间的线性函数表示分组准备时间和任务处理时间，在最小化任务处理时间表长和最小化任务总完工时间的目标要求下，分别提出了确定最优单机器分组调度方案的多项式时间算法。2．处理时间可变影响为指数函数形式的分组调度
近年来，一些学者同时考虑了任务分组技术和指数函数形式的处理时间可变影响。Lee和Wu(2009)将分组准备时间表示为分组位置的指数函数，任务处理时间表示成任务正常处理时间、任务组位置指数函数、任务位置指数函数的乘积，在最小化任务处理时间表长和最小化总完工时间的要求下，分别得到多项式时间算法求得最优的单机分组调度方案。Zhang和Yan(2010)改进了Lee和Wu(2009)的任务处理时间函数模型，把任务处理时间表示成任务正常处理时间的线性函数、任务组指数函数、任务排序位置指数函数的乘积，分别给出了在最小化任务处理时间表长与最小化总完工时间的目标要求下求得最优单机分组调度方案的多项式时间算法。Wang和Wang(2011)在Zhang和Yan(2010)的任务时间可变影响模型基础上作了进一步改进，提出了任务分组时间的复合函数模型，证明得到所研究的单机分组调度问题都是多项式时间最优可解的。3．处理时间可变影响为一般函数形式的分组调度
不同于考虑特殊函数形式的处理时间影响模型的分组调度研究，近年有少量文献关注了考虑不限定为特殊函数形式的一般性处理时间可变影响的分组调度研究。Bai等(2012)在其任务分组调度研究中运用了Yin等（2009）提出的一般性任务处理时间模型和一个线性函数形式的分组处理时间模型，分别在最小化任务处理时间表长和最小化任务总完工时间的成本要求下，给出多项式时间算法求得最优分组调度方案。Yu等（2012b）建立了不含特定线性函数形式和指数函数形式的一般性任务处理时间模型和任务分组准备时间模型，分别在最小化单机器任务处理时间表长、最小化单机器任务总完工时间以及最小化平行机总负荷等目标要求下给出求得最优分组调度方案的多项式时间算法。1.2.4 生产与配送集成调度
Chen和Vairaktarakis(2005)以及Pundoor和Chen(2005)认为，生产-配送的集成调度要好于传统的先考虑生产调度再考虑配送调度的各自独立考虑的调度。Erengucet等（1999）在论述生产与分销供应链时，指出生产和配送的集成调度不仅对生产和配送中的单环节有好处，对供应链整体也有益。Bilgen和Ozkarahan(2004)与Chen(2004)也有类似观点。本小节将分别从早期集成调度模型、五阶段集成调度模型两个方面对相关生产与配送集成调度的定量研究成果进行综述。1．早期集成调度模型及研究
在集成调度五阶段模型出现之前，一些早期的文献采用了定量的调度模型研究了产品生产与配送集成调度问题。Hall和Potts(2003)在最小化生产和配送总成本的目标要求下，建立了产品生产调度、产品分组包装和产品配送交付的单个供应商多个制造商的树形供应链协调模型，设计了求解生产与配送任务调度优化方案的动态规划算法。针对计算机和餐饮服务行业中产品生产完成后需要即刻配送给顾客的情形，Chen和Vairaktarakis(2005)建立了产品生产后即刻配送情形下的产品生产和配送集成调度模型，分别在最小化配送任务完成的平均时间和最小化总配送客户服务绩效的目标要求下，给出了求得单机器情形和平行机情形的最优调度方案的精确算法，也给出了求得近似最优调度方案的高效启发式算法。类似于Hall和Potts(2003)、Chen和Vairaktarakis(2005)、文献Pundoor和Chen(2005)、Li和Vairaktarakis(2007)也关注了有关交易双方的总配送成本和客户服务绩效的集成生产-配送调度模型。Li和Ou(2005)研究了考虑配送车辆具有容量限制的单机器生产、供应及配送集成调度模型，在最小化任务完成时间表长的要求下，证明了一般情形下问题的强NP难性，给出在任务序列处理时间给定情形下求得最优调度方案的是多项式时间算法，也给出了在一般情形下的求得近似最优调度方案的启发式算法。类似地，文献Lee和Chen(2007)、Geismar等（2008）也建立了考虑交付车辆可用性限制条件下的生产与配送集成调度的优化模型，并提出多项式时间算法求解所研究的产品生产与配送集成调度问题。另外，文献Stecke和Zhao(2007)、Chen和Pundoor(2009)基于总受服务水平约束，以最小化运输成本为目标，建立了产品生产与配送集成调度模型，设计了求解生产与配送任务调度优化方案的多项式时间算法。针对最大化产品生产与配送收益的要求，文献Garcia等（2002）、Garcia和Lozano(2005)提出了基于配送时间约束的生产与配送的集成调度模型，结合分支定界方法设计了求得集成调度优化方案的启发式近似算法。Lee和Strusevich(2005)整合了两个不同工厂之间的合作加工和产品配送，把产品加工与配送归结为最小化处理时间表长的目标要求下的两个机器的车间调度模型，在至多两个配送工具情形下给出了求得近似最优调度方案的多项式近似算法，并分析了算法的最坏情况比。针对工业胶粘材料的生产与配送集成调度，Amstrong等（2008）在生产效率以及运输点之间的运输时间给定的条件下，建立了单个运输商多个顾客的集成调度模型，在最大化顾客总需求满意度的决策目标下，通过对下界设置启发搜索的办法设计了求得最优调度方案的高效分支定界算法。2．五阶段集成调度模型及研究
Chen(2010)从生产机器、生产特征、配送特征、顾客数量、决策目标等五个方面表述生产与配送的集成调度，提出了五阶段集成调度模型。针对独立即时配送、同顾客任务集中配送等情形的产品生产与配送的集成调度，Chen(2010)给出了求得最优调度方案的多项式时间算法及算法的计算复杂度。基于Chen(2010)的生产与配送的集成调度的五阶段模型或量化思想，一些近期的文献研究了具体商业模式或企业运作中的产品生产-配送调度。Zhong等（2010）针对委托交付商业模式下的生产-配送集成调度，提出了求得近似最优调度方案的启发式算法。Steinrücke(2011)针对铝冶炼厂的生产和运输调度，提出了混合整数决策模型，并设计了求得近似最优的调度方案的高效启发式算法。Christiansen和Fagerholt(2011)针对大型水泥生产商多种散装船只运送多种规格水泥情形的生产与海运集成调度，将设计的启发架构嵌入遗传算法，在合理的时间求得高质量的水泥生产与海运集成调度方案。Behnam等（2012）针对Yamaha摩托车挡泥板的生产与配送集成调度，提出了相应的生产-配送两阶段集成调度的混合整数动态规划模型，设计了遗传算法求得满意的集成调度方案。
一些新近的文献基于集成调度的五阶段模型及记法讨论了考虑任务工期或时间窗的产品生产与配送调度研究。Leung和Chen(2013)研究了给定配送车辆且给定配送工期的单生产线的集成调度，给出了得到最优调度方案的多项式时间算法。针对生产准备时间与生产机器相关以及配送准备时间与运输车辆装载容量相关的情形，Ullrich(2013)基于集成调度五阶段模型的变化形式，研究了考虑时间窗安排的生产与配送的集成调度，给出了求得近似调度方案的遗传进化算法，并通过算例验证了算法能在合理的时间内得到满意的调度方案。该文献也是唯一被发现的同时考虑处理时间可变影响和产品生产与配送集成调度的研究文献。1.3研究内容与研究方法1.3.1 研究内容和结构安排
本书在任务处理时间可变的影响下，分别在考虑机器维护、产品分组调度技术以及生产与配送集成调度等情形中，对产品调度顺序决策、相关调度算法构建等问题进行分析。首先，研究生产机器维护、两个协同代理、任务分组等情形下的生产调度研究；接着，研究单个顾客情形、多个顾客情形下的产品生产与配送集成调度问题。全文研究分为9章，每章的主要研究内容如下。
第1章，绪论。首先从我国制造与物流配送的低效率的现状，以及时间可变影响在产品生产与配送调度过程中的普遍存在性等两个方面阐述选题背景。其次，从理论和实践两个方面阐述了本书的研究意义。再次，对相关研究成果进行综述。最后，介绍全文的研究内容、研究方法以及研究特色。
第2章，计件维护调度。本章首先建立了机器计件维护的单机调度模型，接着在一般性函数形式的任务处理时间可变的影响下，对调度模型的求解思路进行分析，最后分别在最小化任务处理时间表长、最小化完工时间总和以及最小化调度总代价等目标的要求下，给出求得最优调度方案的多项式时间求解算法，并分析了算法的计算复杂度。
第3章，协同代理调度。本章首先建立了任务处理时间可变影响下两个协同代理的单机调度模型，接着从得到备选调度方案集合的角度对调度模型进行分析，给出求解调度模型的基本思路，而后针对只考虑协同代理的单机调度，给出多项式时间最优求解算法，并分析算法的计算复杂度，最后针对同时考虑协同代理和计件维护的情形，研究给出求得最优调度方案的求解算法及其计算复杂度。
第4章，周期维护调度。本章首先在任务处理时间可变影响下建立机器固定周期维护的单机调度模型，接着分别从多项式近似求解算法和混合进化求解算法两个方面，分析求解调度模型的算法研究思路，而后分析求解调度模型的多项式近似算法的计算复杂度、最坏情况比及表现界，最后给出求解周期维护的单机调度模型的混合进化算法，并给出算例验证算法的有效性。
第5章，任务分组调度。本章首先构建在任务处理时间可变和机器准备时间可变的情形下单机分组调度模型和平行机分组调度模型，然后分别给出分组内的任务的最优排序方法并进行分析，而后针对单机调度的情形，研究在最小化任务处理时间表长的目标要求下求得最优调度方案的多项式时间算法，最后针对平行机调度的情形，研究在最小化机器总负荷的目标要求下求得最优调度方案的多项式时间算法。
第6章，上限约束调度。本章首先建立了带有上限的一般性位置依赖的任务加工时间模型。对于单机调度问题和平行机调度问题，研究的目标函数分别为最小化处理时间表长、最小化总处理完成时刻和最小化机器总负荷。接着，本章通过分析证明把所研究的问题模型转化为经典任务分派问题，分析了各个问题最优求解的计算复杂度。
第7章，拒绝惩罚调度。本章研究了考虑老化影响和拒绝惩罚的一类单机调度问题。在加工过程中每处理完一定数量的任务需要更换原料。任务的处理时间及其完工时刻的权重假设服从给定的关联条件。调度的决策目标是要使得总加权完工时间、总拒绝惩罚和计件原料更换代价的总和最小化。本章首先设计一个动态规划方法求解问题，然后证明所研究的问题是一般难度的NP难问题，最后，把设计的拟多项式算法转化成纯多项式近似方案（FPTAS）。
第8章，单顾客集成调度。本章首先分别建立任务处理时间老化影响的和式模型以及乘式模型，根据给出老化影响模型构建单顾客集成调度的和式模型以及乘式模型，然后从集成调度与生产调度的等价性角度，分析求解集成调度模型的思路，而后在最小化配送任务完成时间的目标要求下求得集成调度和式模型的最优调度方案的多项式时间算法，最后针对集成调度乘式模型，给出在最小化配送任务完成时间的目标要求下求得最优调度方案的多项式时间求解算法。
第9章，多顾客集成调度。本章首先分别建立时间可变影响的单生产机器多顾客和多生产机器多顾客两种情形下的集成调度模型，然后分别分析单生产机器多顾客情形下多项式最优算法求解思路和多生产机器多顾客情形下的遗传进化算法求解思路，而后结合独立即时配送模式的性质，分析求得单生产机器多顾客的集成调度模型的最优调度方案的多项式时间算法，最后设计多层编码的遗传算法求解多生产机器多顾客集成调度模型，并通过算例验证算法的有效性。
全文的研究内容中，第2~9章是研究的主体，围绕处理时间可变影响的调度展开研究。其中，第2~7章的研究可视为生产调度，分别结合机器维护、两个代理、产品分组、处理时间上限约束、拒绝惩罚等因素进行研究；第8章和第9章研究的是产品生产与配送集成调度，其中第8章是单个顾客情形的集成调度，第9章是多顾客情形的生产与配送集成调度。
全文主体章间的关系结构如图1-1所示。图1-1 本书主体章间的关系结构图1.3.2 研究方法（1）定性阐述和定量分析相结合。本书对于老化影响、学习影响及时间可变影响等基本概念进行定性描述。如1.1节研究背景阐述以及1.5节协同代理含义阐述等都采用了定性阐述。另外，本书主要采用的是定量研究方法，首先通过符号描述相关变量，建立调度问题的数学模型，然后研究问题的定量求解算法。如2.2节最小化处理时间表长的计件维护调度，及2.4节最小化完工时间的计件维护调度等研究采用的都是定量研究。（2）运用理论证明的方法。对于生产调度问题的多项式最优算法、近似算法及其复杂度分析等采用理论证明的方法。如2.5节协同代理的计件维护调度算法的复杂度分析，以及3.3节周期维护调度问题的LS算法计算复杂度及最坏情况比分析都采用理论证明的方法得到结论。（3）数值算例与理论比较相结合。运用数值算例说明算法求解问题的有效性。如4.5节通过数值模拟算例说明混合进化算法求解周期维护调度问题的有效性，5.5节通过模拟计算说明提出的多项式算法能高效求得所考虑的分组调度问题的最优调度。另外，运用理论比较方法分析调度算法的表现。如4.4节从调度方案表现上限的角度分析比较LS算法、LPT算法及MLPT算法求解周期维护单机调度问题的表现。1.4本书研究的特色
本书研究的特色主要体现在以下5个方面。（1）改进现有的处理时间可变的函数模型。现有的调度研究很少考虑更具普遍实用意义的不含特殊函数结构的一般性任务处理时间函数模型，且没有考虑不同任务安排在不同机器具有不同的不含特殊函数结构的一般性任务处理时间函数情形下的调度。本书分别在第2章和第5章中考虑不含任何函数结构且不限制单调性的一般性老化和学习综合影响的一般性任务处理时间函数模型，不同任务安排在不同机器时赋予不同的任务处理时间函数。基于给出的一般性任务处理时间函数模型，本书在第2章和第5章分别结合计件维护调度、分组调度进行研究，并分析求得调度方案的多项式时间求解算法。（2）把机器计件维护结合到调度研究中。现有的调度研究大多考虑机器固定周期维护或给定时间区间的维护，很少有研究把机器计件维护结合到调度研究。本书在第2章阐述了机器计件维护的含义，研究计件维护时间可变的生产调度。本书在第3章研究同时包含协同代理和计件维护的生产调度，并分析求得最优调度方案的多项式时间算法。（3）把处理时间可变影响结合到任务分组、上限约束、拒绝惩罚的调度研究中。现有调度研究较少结合考虑一般性任务处理时间可变影响和任务分组技术。本书在第5章分别使用不含特殊函数形式的一般性函数描述任务实际处理时间和任务实际分组准备时间，并基于给出的一般性时间可变影响模型，分别在最小化单机任务处理时间表长和最小化平行机总负荷的目标要求下，研究求得最优调度方案的多项式时间算法。第6章结合处理时间可变影响和时间上限约束，研究求得最优调度方案的多项式时间算法。第7章结合处理时间可变影响和拒绝惩罚因素，研究了求得近似最优调度方案的多项式时间近似方案（FPTAS）。（4）从理论上改进了求解机器周期维护的单机调度的近似算法研究。已有文献只从最坏情况比的单个角度研究求得机器周期维护的单机调度方案的近似算法。本书第4章在最坏情况比、算法计算复杂度以及算法表现界等三个角度全面地研究求得机器周期维护的单机调度方案的近似算法，再结合得到的近似算法的分析结论设计求解问题的混合进化算法求得近似最优的调度方案。（5）把任务处理时间可变影响结合到产品生产与配送集成调度中。定量的生产与配送集成调度研究是近年才开始研究的，结合一般性任务处理时间可变影响的产品生产与配送集成调度研究极少。第8章结合任务独立即时配送性质和第2章、第5章研究得到的任务处理时间可变的生产调度结论，研究任务处理时间可变的单个顾客的产品生产与配送集成调度，在给定条件下得到多项式时间的最优求解算法。另外，第9章运用多层代码的遗传进化算法，求解任务处理时间可变的多生产机器多顾客情形的集成调度的近似最优调度方案。1.5调度概念、符号及方法
本节简要介绍全文涉及的调度概念、符号记法及文中研究将要用到的一些典型调度方法。1.5.1 基本调度概念1．生产调度
调度是指在给定时间里把资源分配到各种任务以优化一个或多个决策目标的过程（Pinedo，2002）。除特别说明外，绝大多数调度研究一般都归结为生产调度研究。生产车间中的工件加工生产、楼房建筑工地的工程建设、上课教室的时间安排、运送货物的火车时刻设计、空运飞机的航班设计，以及飞机在机场降落时的跑道安排等问题，都可以抽象为在给定时间里把特定机器资源分配到特定任务以最优化决策目标的生产调度。具体地，产品生产与配送调度可能包含生产材料准备、资源分配、配件生产、产品组装、机器维护、产品检测、产品装载、配送车辆选择、路径选择、配送时间安排等很多步骤和环节。
本书不具体研究每一个步骤和环节，把产品生产与配送调度看做由产品生产和产品配送两个基本环节组成。在研究单个环节的调度时，不论是产品生产的调度，还是产品配送调度，本书都将其抽象并称为生产调度。2．生产与配送集成调度
相对于把产品生产环节、产品配送环节分开独立优化的调度研究，本书把同时考虑产品生产环节及产品配送环节联合优化的调度称为产品生产与配送集成调度。3．竞争代理与协同代理
实际运作常常会遇到考虑多个代理的调度。每个代理都包含一组需要处理的任务，且每个代理具有各自的目标函数，每个代理为了各自的目标竞争使用生产机器资源，这时代理之间是相互竞争的关系，被称为是竞争代理。在实际的调度过程中，不同的代理之间不仅会为了各自目标竞争使用产品生产或配送的资源，也会在调度过程中相互协作使得共同的决策目标达到最优。本书将这种在相互竞争的同时又相互协作的代理称为协同代理。1.5.2 基本调度记法
本节将分别介绍生产调度调度α|β|γ三阶段模型以及生产与配送集成调度α|β|π|δ|γ五阶段模型及相关的概念、符号。1．生产调度的α|β|γ三阶段模型
针对大量的生产调度研究，Graham等（1979）提出了标记调度研究的三阶段模型，用三元的有序数组α|β|γ来表示研究的调度问题。α表示机器环境特征，β表示任务加工的特征和条件限制，γ表示生产调度决策目标。（1）机器环境特征（α域）介绍
下面列举几种常见的机器环境特征（α）及其记法。
单机器（1）表示所有任务依次由单一一台机器进行加工。
平行机器（m）表示任务j的处理可以在m台机器中的任意一台上进行处理。m
并行同速机器（P）表示任务j在每一台平行机器上处理的速度是相等的。m
并行恒速机器（Q）表示m台平行机器具有各不相同的处理速i度。机器i的处理速度为v。如果任务j在机器i上处理，其所需处理时ijiijj间为p=p/v。p表示任务j在机器i上完成处理所需要的时间。当只有一ij台机器或者任务j处理时间不受机器影响时，p下标i可以被省略，简jm记为p。如果所有机器的速度相同，那么机器环境Q和前一种机器环m境P相同。mm
并行变速机器（R）是并行恒速机器（Q）基础上的一般化情形，指每项任务在各个机器上的处理速度各不相同。机器i处理任务jiijijjj的处理速度为v，则任务j在机器i上处理所需的时间为p=p/v。（2）调度特征（β域）介绍
β域表示任务处理过程中的调度特征及条件约束。下面列举β域中几种常用的记法。jj
提交日期（r）出现在β域中表示任务j不可以在其提交日期r之前j开始处理；反之，如果r没有出现在β域，则表示任务j可以在整个操作过程开始的零时刻之后的任何时候开始处理。
可中断（prmp）表示任务处理一旦开始就必须在完成之前允许中断，或没有必要一直把任务在处理完成之前保留在机器上。jj
机器可用性限制（M）。M出现在β域表示不是全部的机器可以用来处理任务j。类似地，部分调度研究考虑了机器因维修而不可用的情形，大多用M表示。
不允许等待（nwt）。β域中出现nwt，表示任务处理不可以在任意的两台连续的机器之间等待，一般用于流水车间调度问题中。（3）生产调度目标（γ域）
γ域表示生产调度的决策目标，一般只包含一项。接下来介绍γ域中常见的调度决策目标。max
处理时间表长（C）是系统开始处理任务到完成全部任务所需j时间。任务j处理完成时间记为C。如果记第一件任务开始处理时间为max零时刻，则C等于最后一个离开处理系统的任务的完成时刻，即maxjC=max{C, j=1, 2, …, n}。max
最大延迟完工时间（L）用来度量违反工期最严重的情形，等j于所有任务交货延迟时间的最大值。工期（d）表示任务j的工期是指j该任务预定的生产完成时间。晚于工期d完成任务处理，将被施加一定的惩罚（penalty）。如果某个工期必须被遵守，则称为最后期限maxj（deadline），记作。由此，最大延迟完工时间为L=max{C-jd, j=1, 2, …, n}。
总加权完成时间等于所有n项任务的完成时间的加权求和，用来表征调度引起的所有库存或等待成本的指标。
下面给出两个使用三阶段生产调度模型表述调度问题的例子。max
调度问题1|M|C表示任务在单个生产机器进行生产，需要考虑机器维护的情况，决策目标是要最小化任务处理时间表长。mmax
调度问题P|prmp|C表示所有任务在m台平行生产机器处理，每项任务处理过程是可中断的，决策目标是要最小化任务处理时间表长。2．生产与配送集成调度的α|β|π|δ|γ五阶段模型
试读结束[说明：试读内容隐藏了图片]