基于松弛时间窗的加工速率可变的调度问题

毕业论文：正文 毕业论文（设计）正文题目：基于松弛时间窗和额外资源的加工时间可变单机调度问题学 院：专 业：班 级：学 号：学生姓名：指导教师：二xx年 五 月第1章 绪论1.1 课题背景准时制生产（JIT，just in time），又称为无库存生产（stockless production），也叫做零库存（zero inventory）。这种管理模式产生于上世纪70年代，由日本丰田汽车公司提出，是一种基于库存管理和控制的现代精练管理模式，在精确测定生产各工艺环节提高作业效率的前提下，按订单确定的时间对生产实行控制，以消除一切无效作业与浪费为目标（Kramer&Lee(1993)），在日本及中国的许多企业广泛实施，并取得巨大的成效。带时间窗的排序调度问题正是在JIT的思想下形成的。排序（scheduling）问题是一类重要的组合最优化问题，它是通过利用一些控制器（processor）、机器（machine）或资源（resource），达到最优地完成一批给定的任务（task）或工件（job）。它主要是在机器制造的背景下产生的，后来被广泛应用于航空航天、交通运输、企业管理、医疗卫生、计算机科学等多个领域。有关排序理论的研究是从二十世纪五十年代初开始的，普遍认为是从Johnson（1954）开启了经典排序调度研究的篇章，经过了不断发展改进，形成了运筹学领域一个十分活跃的研究方向。本文主要先从交货期设置的发展的角度出发，整理归纳国内外的相关文献。逐步引入现实因素，如：经过维修之类活动后，工件加工速率改变；设施在加工过程中会出现老化现象；对设施、工件分配额外的资源会改变效率等方面，将排序调度问题，从初始的模型扩展成综合复杂模型。1.2 研究意义1.2.1 理论意义调度和排序问题是决策的一种形式，受到越来越多的关注。在目前的竞争环境中，有效的决策安排已经成为制胜法宝。公司必须满足其向顾客承诺的交货期，不然会造成重大的信誉损失，同时，他们也必须以科学的方式计划各项活动，使成本最低。对于调度问题，在20世纪初期，开始在制造业中受到重视。60年代时，人们用动态规划和正数规划对调度问题建模方面做了大量的工作。而从Richard Karp发表了关于复杂度理论的论文后，70年代的研究工作主要集中在了调度问题的复杂度层次。80年代，随着人们对随机调度问题的关注度的增加，学术界和工业界在不同方向展开了研究。同时，随着计算机技术的不断发展，个人计算机开始广泛应用于制造设备中，人们开发除了生产实际可用的调度计划的系统，因此，解决该类问题具有极其重要的理论意义。1.2.2 现实意义参阅英文出版物Scheduling: Theory, Algorithms, and Systems,由美国学者Michael Pinedo所著，理解了在现实中调度问题的意义，从整个生产加工的角度理解调度问题。在现代化的生产制造企业中，都存在相当完善的信息系统，包含一台中央计算机和数据库。通过ERP系统在所有组织水平上实现企业和决策支持系统的横向连接。在一般的制造环境中，制造部门提交的订单必须细化成带有工期的工件，这些工件通常在一个带有处理器的机器上以特定的次序进行。机器在加工过程中，可能会因为老化或其他因素，造成加工速率减慢，工件可能就会延迟；如果对机器执行维修活动，会暂停工件的加工，而维修的时间也可能会受到不同因素的影响，经过维修后，机器的加工速率又会发生改变；车间里，如果需要赶工，就可能增加额外的劳动力之类的，类似情况都必须加以考虑，因为它们可能对调度产生重大影响。对于调度过程，除了车间的影响外，它同样受到处理整个企业中长期规划的生产计划的影响。这个过程试图在库存水平、需求预测和资源需求的基础上，优化公司的所有产品组合和长期资源分配。在制造业中，调度活动与工厂里的其他决策活动进行交互，在一个调度计划生成之后，必须使原材料和资源在特定的时间内可用。调度计划在物料需求计划（MRP）系统中的作用举足轻重。第2章 生产调度研究现状分析2.1 交货期研究现状在传统的调度模型中，通常假设工件的交货期固定。但通过Smith等（1986）调查了美国制造业公司后，他们发现在生产调度中找到合适的交货期至关重要。而在理想状态下，制造商和客户都希望可以准时交货，达到零库存的目的。但是由于生产条件的限制，工件存在不能按时完工的情况。提前完工的工件可能会产生仓储、保险等费用，误工的工件会导致顾客不满意，可能会产生赔偿、流失订单等费用。因此Gupta等(1987)、Cheng等(1988a,1990）设定提前完工及误工的惩罚因子，符合JIT的概念，在制造商综合决定交货期时，尽量达到准时交货的目标。如Liman等（1998）。2.1.1 交货期分类对于交货期的设置，最早可以追溯到Jackson(1955)，而参考Gupta等（1990） 的文献，可以得知，最早系统性研究due-date的调度问题是Conway（1965），随后研究学者将此类问题运用计算机仿真。due-date调度模型中交货期的设置最初有三种不同的方法：(i) constant flow allowance (CON)，(ii) slack time (SLK)，(iii) total work (TWK)。此后，根据Gordon等(2002)延伸的各类交货期安排的方法，又得到了(iv)processing plus wait(PPW),(v)number of operation(NOP)等。归纳整理各类交货期设置的方法关系如图2- 1： 图2- 1 due-date方法归纳CON due-date是交货期设置的方法中最基础的一种，对于所有的工件，给定一个共同的交货期（记为k），这种通过设置交货期的方式表示了工件的传送到达过程。SLK due-date交货期设置中所有的工件都给定一个公用的参数来表示松弛或等待时间（记为q），这种交货期方法通过简单的设置一个松弛参数。TWK due-date交货期设置则表示了另一种可能的交货期方式，交货期由生产设施安排，根据总的工作内容确定。PPW due-date交货期的设置结合了SLK和TWK的方法，最优的调度方案需要同时确定k和q的值。NOP due-date方法中的交货期在工件j执行次数的基础上决定的。此外，还有SRPT(shortesr remaining processing time) due-date方法，每个工件都有很短的滞留时间选择下一个处理工序。2.1.2 一般交货期在制造业中，人们更希望交货期是一个确定的时间区间（due-window）,而不是一个单个的时间点（due-date）（Kramer&Lee（1993）。Due-date模型是一种特殊的情况（时间区间为0），而Due-window模型则是更一般的模型，due-window定义为工件完成的时间区间。如果工件在这个区间内完成则为准时，不需要任何惩罚。否则，如果在时间区间提前或延后完成，都需要惩罚，如库存保管费、顾客流失费用等。due-window是due-date更一般化，符合现实生产的模型。在调度问题中，存在多种在时间区间内执行工件活动的模型。然而，大多数的模型都是严格约束条件，即工件不能在时间区间外操作，此类模型给定一组可用的平行机和每个工件的固定开始时间、完成时间，目标是确定是否存在可行的调度策略或确定最少的所有工件加工完成所需要的处理器数量或总利润最大化等（见Janiak（2012）。如果时间间隔与前面的工件无关，此类问题则称带时间窗的排序调度问题。如上面介绍的严格约束的情况，称为硬时间窗。反之，称为软时间窗。软时间在接受惩罚后，允许在时间区间以外执行工件任务，主要用于运输和物流领域（船舶调度、车辆路径等），本文的due-window主要指软时间窗的模型。大多数求解due-window的问题都是求解最小多元目标函数，包括提前完工惩罚、误工惩罚、交货期位置、时间窗的大小等（见Hoogeveen（2005）我们通过横向查阅以SLK due-window为基础的相关文献，目前认为开始研究SLK due-window的模型是从Mocheiov(2010)开始的，他们讨论了SLK的最基础的模型，目标函数只包括提前成本、误工成本、时间窗位置成本和时间窗大小的成本，使目标函数极小化。2.2 生产调度速度影响因素在排序调度问题中，制造商的总收益除了与交货期有关外，还涉及了其他方面。如在工件加工过程中，机器设备由于连续使用，会出现一定程度的磨损，出现老化现象，影响加工效率，从而影响总收益，制造商可以选择通过分配额外的资源，如增加劳动力、电能等，弥补由于老化现象造成的收益降低，或者通过维修活动，使设施恢复初始状态或者加工效率提高等方式。最终都是为了达到提高收益的目标。2.2.1 维修活动在调度问题中，除了交货期的安排外，还涉及了其他因素。在一些现实制造系统中，机器在经过保养、阶段性修理或者部件更换后，会回到初始状况，或者加工效率提高。对于这种现象，研究学者将其归纳为一类加工速率会发生改变的调度模型（RMA）。最早研究RMA调度问题的模型是Lee和Leon(2001)，他们认为维修活动的时间为一个常数，且它与工件相关，会影响工件处理时间。我们在求解有关给定维修活动进行的位置的模型时，可以将该问题简化成标准分配问题。这些位置的数量明确限定在n以内（工件的数量），这意味着解决方案的总体时间复杂度为On4（包括n个决策问题）。2.2.2 加工恶化效应传统的排序调度模型通常假定工件的加工时间是一个固定常数。但是，在现实中，会由于很多因素影响工件的加工时间。恶化效应正是其中之一，恶化效应最早由Mosheiov（2001b）提出，他认为工件的加工时间是由已经排序的工件的数量决定的单调不增的指数函数。恶化效应正如Rudek等（2011）解释的那样，假如在强浸蚀的环境下，化学制品加工活动中亚铁盐的数量会由于化学反应增加，然而有效物质的浓度会降低。换而言之，酸洗槽设备老化，可以用加工恶化的模型表示。为了阻止这种消极的状态，我们可以采用加热设备的方式（使用电能或燃料）或者不停的晃动酸洗槽（也需使用电能），这两种方法可以用下文的资源配置模型表示。2.2.3 额外资源配置工件的加工处理时间还可以通过配置资源的方式改变，如对设施或工件使用额外煤气、燃料、电能或者人工劳动力。第一个提出资源配置问题的可能是Vickson（1980），他假设工件的处理时间是其分配的资源的线性函数。工件的处理时间和工件处理的成本之间是相对立的关系，假定有额外更多的资源（如支付更多的成本），会减少工件的处理时间。通过查阅Shabtay等（2007）关于调度问题可控的处理时间的文献综述，可以发现在大多数的加工时间可控的模型中，研究学者通常假设工件的实际加工时间是资源额外分配的数量的相关线性函数。2.3 本章小结科学研究一般都遵循归纳、演绎的方法，先将现实中一个复杂的模型，归纳出最核心的共同的情况和目标，通过一个简单的模型、例子，抽象出这一类问题的概念。随后，用演绎的方法，逐渐将一个理想状态下的特殊情况，扩展成一般的模型，本文调查思路也如此。研究学者们，在基于交货期的问题上，扩展了资源配置、恶化效应、设备加工速率会改变、资源约束等一般情况，将初始模型更加复杂化。在考虑了不同情况后，有一些研究学者，尝试将这些不同情况，综合在一个模型中，如Min（2013），在CON due-window的基础上，综合考虑了老化效应、设备加工速率改变、资源配置的调度模型。也有部分研究学者，将单机单个加工的排序调度模型从扩展成批加工机器排序，在一个机器中可以同时加工多个工件，如在大规模集成电路的生产测试中，最后要将多个工件同时测试等情况。还有些研究学者，致力于研究不同开始加工时间的情况等，也可以将单机环境扩展成平行机环境等。研究的最终目的都是为了将模型尽量还原成现实情况。参考了各类学者的研究思路，借鉴同类文献的模型、目标等，本文拟定的研究方向是基于SLK due-window的基础上，尝试将设备加工速率改变、老化效应、资源配置三者结合起来，构造出一个复杂多目标的模型。第3章 基于松弛时间窗的加工速率可变的调度问题3.1 问题描述3.1.1 符号说明本文使用的符号如下：n工件的数量J=J1，J2，Jn工件序列Pj工件Jj的正常加工时间Pj未执行维修活动时工件Jj的实际加工时间PjR执行维修活动后工件Jj的实际加工时间aj0工件Jj的加工恶化效率uj工件Jj所增加的额外资源的数量uj工件Jj能增加的额外资源的上限bj工件Jj由于增加额外资源而增加的效率v一个自己设置的正数ft维修活动的持续时间b0维修活动的初始需要时间c0维修活动的恶化速率t维修活动的开始时间i维修活动执行的工件的位置j00每个工件的提前期的单位成本0每个工件的误工情况的单位成本0时间窗开始时间的单位时间成本0时间窗大小的单位成本决策者规定的关于额外资源的常量为Gj额外资源的单位成本3.1.2 模型说明本文模拟了单机的环境下n个独立的工件的情况。设工件j的基本加工时间为Pj，j=1,n。工件加工时间呈线性恶化趋势，即件加工时间为Pjraj,其中 raj为工件Jj位于位置r的恶化函数（aj0）。另用bj、uj表示额外资源的效果，uj为工件Jj所增加的额外资源的数量，bj为工件Jj加工速率增加的。因此，工件Jj在未经过维修活动前的加工时间Pj可以表示为：Pj=Pjraj-bjuj ，j=1,n0ujuj0 v为正指数为了抵消工件的恶化效应，调度程序模拟执行维修活动，改善工件的加工效率，即每次经过维修后，工件的处理时间变为jPj，其中j(0j1)为工件Jj的加工效率变化参数(j=1,n)。经过维修后，工件Jj的加工时间Pj改变为：PjR=jPjr-iaj-bjuj ，j=1,n对于维修活动，本文假设维修时间为常数T=b。接着，考虑与维修开始位置相关的恶化模型，如果维修活动安排在第i个位置之前，它的持续时间为：ft=b+ct=b+cCi=b+cp1-b1u1+p22a2-b2u2+ +piiai-biui，对于一个给定的工件序列，工件Jj的完成时刻记为Cj，j=1,n。每个工件都有它自己的时间窗：dj1,dj2,dj1dj2，r=1,n）。第j个工件的提前期为Ej=max0,dj1-Cj，延迟期为Tj=max0,Cj-dj2。假设交货时间窗的大小是可调节的，第j个工件的时间窗的开始时间等于工件的加工时间加上于工件无关的常数：dj1=Pj+q1 同样的，第j个工件的时间窗的结束时间等于工件的加工时间加上于工件无关的较大常数：dj2=Pj+q2 因此，第j个工件的时间窗为：Pj+q1,Pj+q2用Dj表示第j个工件的时间窗的大小，Dj=q2-q1D，j=1,n。另外，每个工件的时间窗的大小都是相同的。参照Liman等(1998)提出的模型，目标函数中包含了四个组成部分：()提前期，()延迟期，()时间窗的开始时间，（）时间窗的大小。工件加工完早于规定交货时间窗的的单位成本为，工件加工完迟于规定交货时间窗的单位成本为，工件交货时间窗的位置单位成本为 ，时间窗的大小单位成本为。加入额外资源因素，目标函数中增加资源成本，额外资源的单位成本为Gj，决策者规定的关于额外资源的常量为。因此，最小化目标函数为：fd，D，u=j=1nEj+Tj+dj1+Dj+j=1nGjuj借鉴Min（2013）、Gang（2014），我们将研究问题化简成如下模型：1/rma,Pjr=Pjraj-bjuj/j=1nEj+Tj+dj1+Dj+j=1nGjuj;1/rma,Pjr=Pjrajujv/j=1nEj+Tj+dj1+Dj+j=1nGjuj上式中rma表示存在维修活动的情况。3.2 初步分析首先，我们可以明确最优的调度方案在零时刻开始，而且在两个连续的工件间不存在闲置时间。引理1.对于所有的j，都存在Cjdj1Cj-1dj-11证明. 对于给定的序列，当Cjdj1时，可以得到：Cj-1+PjPj+q1Cj-1q1Cj-1q1+Pj-1 Cj-1dj-11 引理2.对于所有的j，都存在Cjdj2Cj+1dj+12证明. 对于给定的序列，若Cjdj2时，可以得到：Cj-1+PjPj+q2Cj-1q2Cj-1+Pjq2Cjq2 Cj+Pj+1q2+Pj+1Cj+1dj+12 性质3.对于任意给定的序列，q1、q2的值为第k个工