复杂窗时排序问题及算法研究

图书标准信息

• 作者 赵洪銮 著
• 出版社 科学技术文献出版社
• 出版时间 2018-01
• 版次 1
• ISBN 9787518936441
• 定价 48.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 140页
• 字数 114千字

【内容简介】

 生产调度是根据企业生产系统的生产目标和环境状态，在尽可能满足约束条件（如交货期、工艺要求和路线、资源现状）的前提下，按照工艺规程和计划，通过下达生产计划及调度指令对系统内的可用资源进行实时任务分配，以达到缩短产品的制造周期、减少在制品、降低库存、提高生产资源的利用率及提高制造系统生产率等目的。
影响生产调度问题的因素很多，正常情况下有产品的投产期、交货期（完成期）、生产能力、加工顺序、加工设备和原料的可用性、批量大小、加工路径、成本限制等，这些都是所谓的约束条件。有些约束条件是必须要满足的，如交货期、生产能力等，而有些达到一定的满意度即可，如生产成本等。
为了避免储存及隐藏的额外运转带来的高费用，例如，由于等待、传递、额外劳动力、重加工及订单改变等引起的效益损失，生产商不仅考虑延误带来的惩罚还必须顾及提前完工付出的费用，这就是准时排序问题。它限定工件的交货期：如果工件在交货期之前完工，会出现储存费和保管费之类；而在交货期之后完成，固然要科以罚款，则会产生延误赔偿甚至失去合作机会等损失。而准时排序的目的就是要小化这些费用之和，所以，在“准时”概念中，尽可能使得工件的完工时间接近其交货期或者提前和延误的工件个数尽量少。因此，提前和延误应该尽可能地避免，这也使得以前讨论的传统性能函数无效。既然目标函数是关于工件完工时间的非正则函数，问题的研究相对比较困难。
现实中，供应商和客户在签订供应合同时，通常会指定一个交货时间区间，如果工件在这个时间区间内完成则被认为是准时的，不会招致任何处罚。它是将交货期合理地设置成一个时间段，而不再是单个时间点，这种排序称为窗时排序。我们把这个时间区间称为工件的交货期窗口，该窗口的左端为早交货期（或称“交货期窗口的位置”）、右端为晚交货期。如果工件在窗时交货期前完成，则必须被库存，这种情况视为一个提前处罚。另外，如果工件在交货期窗口后完成，根据合同中的规定，它将导致延迟惩罚。显然，如果交货期窗口较大则可以增加供应商生产和输送的灵活性。然而，设置大型的交货期窗口和延迟工件完成时间都会降低供应商的竞争力和客户服务水平。所以交货期窗口的设置也经常成为问题的目标之一。
本书探讨的内容都是对经典排序的突破，研究现代排序与准时、窗时排序的结合应用，目的是为了在新型排序环境下，使某个衡量函数大或者小，如提前时间、延误时间、提前或延误的工件个数及交货期窗口的确定等。
粗略来讲，有两类相关的惩罚函数。一类目标函数中，提前和延误惩罚依赖于工件是否提前或延误，而不是提前或延误了多长时间。这类问题关注的是提前和延误的赋权工件数。另一类是提前时间和延误时间所带来的惩罚，即与完工时间距离交货期窗口的时间差成正比。此类目标函数既普遍又具备很强的竞争力。另外，交货期窗口的位置和大小也具有一定的决策意义，被很多生产商作为衡量有效性的一个重要指标。例如，决定订单数量及耗费资源计划等，所以它们往往作为决策变量，需要与工件的优序列一起确定。本书探讨复杂生产环境下窗时排序问题的一些特点和解决方法，总结如下。
①就交货期窗口的位置和大小是给定还是待定的几种情况进行了讨论，针对目标函数是关于提前、延误的工件个数或者时间，以及它们的综合目标函数展开研究，充分利用了工件位置的累计权重，并提出相应的有效算法。
②讨论了工件有公共交货期窗口的同时加工排序问题，工件的尺寸大小相同，在交货期窗口给定或其位置待定情况下，以小化总的提前和延误惩罚；并且如果交货期窗口是待定参数时，总费用包含该决策费用。针对两种目标函数分别研究；尤其当批的容量有限时，乃是经典排序的推广。在寻找它们的优算法时，“位置权”已不再有效。
在以前关于同时加工排序问题的研究中，只有几篇文献涉及交货期的存在性，以小化总延误或大延误。本书把窗时排序推广到了多个工件可以被同时加工的情况，目标是要把工件分成多个批、再排列批的次序使得总费用低。在提出优性质和参数分析的基础上，给出了批容量无界时的一些有效算法。研究有界的同时加工排序问题。当提前和延误惩罚系数是任意整数且窗口位置待定时，把3-划分的一个实例转化到该问题，从而证明了它是强NP-完备的。进而提出几个优性质，但优排序已不再满足SPT-批序，问题更加难于研究。
③现实生产中有以下情形：具有相似特征的一些工件需要相同的生产场景和设备，所有工件被分成多个组，于是从加工一个组的工件转化到加工另一个组的工件时需要执行安装任务。正是由于安装任务的介入使得问题更加困难。讨论当交货期窗口给定时以小化赋权提前时间和延误时间总和的问题，问题的复杂性未知。本书探讨了小化提前和延误的工件个数，其中交货期窗口的位置待定或者位置和大小均待定。
④批调度问题中每个工件有其特定的尺寸大小，即差异工件，同一批中工件的总尺寸不能超过批的容量限制，因此，包含在每一批中的工件个数可能不同。研究加工时间、尺寸等参数对费用的影响及优调度所具有的结构特点，并提出了启发式算法，该算法充分利用了参数信息并简便易行。
本书通过对上述研究内容和创新点的讨论，深入分析各种生产环境因素对总费用的影响，建立综合性的目标函数表达式，分析参数特点及优解的结构化性质，得出相应的算法并分析其复杂性。

【目录】

 

 

第1章绪论 /

 

11排序问题的背景及描述 /

 

12现代排序 /

 

13算法中的几个重要概念 /

 

14准时排序及相关结果 /

 

15窗时排序及相关结果 /

 

16符号表示 /

 

17本书的贡献与组织结构 /

 

第2章最小化提前/延误的赋权工件个数 /

 

21引言 /

 

22交货期窗口的位置待定 /

 

23交货期窗口的大小待定 /

 

24交货期窗口的位置和大小均待定 /

 

25给定的交货期窗口 /

 

26推广到多台平行机 /

 

27结语 /

 

第3章最小化提前和延误时间惩罚 /

 

31引言 /

 

32交货期窗口给定 /

 

33交货期窗口的位置待定 /

 

34多个综合目标 /

 

35推广到多台机器 /

 

36结语 /

 

第4章有交货期窗口的无界批处理 /

 

41批处理问题 /

 

42相关研究结果 /

 

43给定的交货期窗口 /

 

44交货期窗口的位置待定 /

 

45结语 /

 

第5章关于非准时工件数的有界批处理 /

 

51问题描述 /

 

52最优性质 /