第5章---生产调度(新)

1、李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第1页,生产运作管理,第5章 生产调度,本章目录,第1节：生产调度与优化 第2节：生产调度问题的符号表示与分类 第3节：常见生产调度问题及其启发式规则 第4节：生产调度问题求解举例,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第2页,第1节：生产调度与优化,(1)调度问题举例 生产调度属于企业的微观管理层次。 企业在组织生产时必须充分考虑到企业内部人力、物力、财力以及企业外部供应链条件及国家法律对生态、环境保护的规定等多方面的约束，在此前提下尽可能利润最大化并提高客户满意度。企业

2、生产过程中存在如下一类问题，主要研究如何充分利用企业内部的生产设备，尽可能提高客户满意度与企业利润，因此需要将待加工的任务或作业分配到一些机器上按照某种次序依次加工，这类问题统称为生产调度问题或排序问题。可见，生产调度旨在充分利用现有一定的资源，在满足一些必须条件的基础上，完成一定的任务并达到特定的调度目标，因此它本身就是一类典型的优化问题。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第3页,第1节：生产调度与优化,(1)调度问题举例 一个车间要加工一批零件，每一个零件都具有相同的工序，即按照相同的顺序在几个不同的机床上加工。每个零件在每个机床上的加工时间

3、可能不同。调度的目标是使得加工完所有零件的时间最短。这是一个流水线调度问题。 在汽车生产的焊装过程中，若干焊装工业机器人在尽量少的时间内完成一个整车3000多个焊点的焊装任务，最后一个焊点的焊装完成时间标志着所有焊装任务的完成，这就对应一个最小化最大完工时间的平行机调度问题。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第4页,第1节：生产调度与优化,(1)调度问题举例 对于这样一些生产调度问题， 我们通常将机床、焊装工业机器人等抽象为机器(machine)； 将零件、焊装点的焊装任务等抽象为作业(job)； 调度问题的一个可行解是一个加工这些作业的序列；

4、调度问题的最优解则是众多可行解中使得目标函数最优的可行解。 生产调度问题是一类典型的优化问题，它旨在充分利用现有一定的资源，在满足一些必须条件的基础上，完成一定的任务并达到特定的调度目标。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第5页,第1节：生产调度与优化,(1)调度问题举例-制造系统中的生产调度：,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第6页,第1节：生产调度与优化,(1)调度问题举例 生产调度是为了实现生产计划的一个资源优化配置问题，是制造业系统中的一个重要环节。然而，调度问题远远不只是生产过程中的调度问

5、题，它广泛存在于计算机系统、交通、医院、学校、服务业等。 服务系统中的生产调度：,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第7页,第1节：生产调度与优化,(1)调度问题举例 一个大型超市共有50个收银台，每个收银台有一个收银员。每个收银员的收银速度（一个单位时间内平均扫描条形码的次数）相对恒定。目标是在尽量短的时间内满足更多用户的收银任务。由于收银员收银速度差异相对恒定，这是一个同类机调度问题。 某高校扩大招生数量，原来针对学生的网络服务器已远远不能满足学生的需要，为了提高网络服务质量，在原先网络服务器的基础上购置了1台新的服务器，并构建了由2台服务器组

6、成的计算机机群（集群）系统。由于这2台服务器之间存在恒定的速度差异，这也是一个同类机调度问题。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第8页,第1节：生产调度与优化,(2)调度问题是优化问题 优化是研究如何充分利用时间、设备、成本、人力等有限的资源，达到某一或某些最优目标的理论，通常采用定量的研究方法。 对于现实生产生活中的优化问题，通常需要为之建立相应的优化模型，从而避免问题定义的二义性，然后在此基础上设计一定的优化算法以获得问题的最优解或高质量满意解。 因此，优化主要包括优化问题与优化方法两个方面，而优化问题一般采用优化模型来描述。,李凯(合肥工业

7、大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第9页,第1节：生产调度与优化,(2)调度问题是优化问题 由于优化模型是实际优化问题的数学描述，因此它也包括目标函数和约束条件两个部分。 根据目标个数不同可以将优化问题分为单目标优化问题和多目标优化问题。 一个单目标优化问题通常可以建立如下典型模型： ，其中是全部解空间，S是解空间中满足约束条件的解的集合，而 是S 中的某一个解，被称为可行解。问题的目标是寻找一个最优解 ，使得 。 目标最大化的优化问题可以转化为目标最小化的形式。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第10页,第1节：

8、生产调度与优化,(2)调度问题是优化问题 多目标优化问题的优化目标多于一个，可以建立如下形式的模型： ， 其中 是一个非空集合， 是一个函数向量，因此多目标优化又称为向量优化。 多目标优化问题通常包含若干具有冲突的目标，因此往往难以保证所有目标同时达到最优。Pareto提出了Pareto最优解的概念，即针对某一决策变量无法找到与之更优的解。由于多目标优化问题具有若干个目标，因此通常具有众多的Pareto最优解，并形成Pareto最优集。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第11页,第1节：生产调度与优化,(2)调度问题是优化问题 由于现实生产生活中

9、优化问题的复杂性和多样化，根据实际问题建立模型时约束条件及目标函数中的变量可能是确定型的或不确定型的，因此又可以将优化问题分为确定型优化问题和不确定型优化问题。 对于不确定型优化问题，又可大致分为随机模型优化问题和模糊优化问题等。 另外，根据解空间的特点还可以将优化问题分为连续型优化问题、离散型优化问题； 根据决策变量的特点可以将优化问题分为线性优化问题、非线性优化问题等。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第12页,第1节：生产调度与优化,(3)调度模型举例 Pm|Cj问题的数学模型：,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度

10、2020年7月9日 第13页,第1节：生产调度与优化,(3)调度模型举例 相同的问题，不同的模型：,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第14页,第1节：生产调度与优化,(3)调度模型举例 更多的生产调度模型见制造工程管理中的优化理论与方法2.2节。 基于分配变量的模型 基于时间间隔的时序变量的模型 基于开始时间的时序变量的模型 更复杂的调度模型，可以采用自然语言与数学符号相结合的方法进行描述。举例(见PDF文档)。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第15页,第1节：生产调度与优化,(4)优化问题(模型

11、)的复杂性 首先看算法的“计算复杂性”，通俗说来，就是用计算机求解问题的难易程度。其度量标准： 一是计算所需的步数或指令条数（这叫时间复杂度）； 二是计算所需的存储单元数量（这叫空间复杂度）。 时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。 时间复杂度越来越受到重视。动态规划相关算法须关注空间复杂度。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第16页,第1节：生产调度与优化,(4)优化问题(模型)的复杂性 将计算问题按照在不同计算模型下所需资源的不同予以分

12、类，从而得到一个对算法问题“难度”的类别，就是复杂性理论中复杂性类概念的来源。 例如一个问题如果在确定性图灵机上所需时间不会超过一个确定的多项式(以输入的长度为多项式的不定元)，那么我们称这类问题的集合为P(polynomial time Turing machine)。 而将前述定义中的“确定性图灵机”改为“不确定性图灵机”，那么所得到的问题集合为NP(non-deteministic polynomial time Turing machine)。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第17页,第1节：生产调度与优化,(4)优化问题(模型)的复杂

13、性 计算复杂性的初衷是理解不同算法问题的难度，特别的是一些重要算法问题的困难性。为了确切的描述一个问题的困难性，计算复杂性的第一步抽象是认为多项式时间是有效的，非多项式时间是困难的。这基于指数函数增长速度的“违反直觉”的特性： 如果一个算法的时间复杂性为2n，取输入的规模是100，在运算速度是每秒1012（关于CPU速度，参见Instructions per second，其中报告截止2009年，主流个人电脑的运算速度可以看作是4*1010每秒）的情况下，该程序将会运行4*1010年，几乎是宇宙年龄。 然而多项式的指数很大的时候，算法在实践中也不能看作是有效的。,李凯(合肥工业大学管理学院)

14、生产运作管理第5章：生产调度 2020年7月9日 第18页,第1节：生产调度与优化,(4)优化问题(模型)的复杂性 如果一个问题的复杂度是该问题的一个实例规模n的多项式函数，则这种可以在多项式时间内解决的问题属于P类问题。通俗地称所有复杂度为多项式时间的问题为易解的问题类，否则为难解的问题。 简单的说，存在多项式时间的算法的一类问题，称之为P类问题；而像梵塔问题，推销员旅行问题等问题，至今没有找到多项式时间算法解的一类问题，称之为NP问题。同时，P类问题是NP问题的一个子集。 多项式时间问题、NP-hard (NP难) 问题、强NP-hard问题 如果一个问题的特例是NP-hard的，则该问题

15、也是NP-hard的。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第19页,第1节：生产调度与优化,(5)常见的NP-难问题 背包问题： 给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。 设有一个容积为b的背包，n个尺寸分别为ai、价值为ci的物品，如何装包使得总价值最大？(0-1背包问题) max 1in cixi s.t. 1inaixi b; xi0,1, i=1,2,n,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第20页,第1节：生产调度与优化,(5)常见的

16、NP-难问题 旅行商问题： 旅行商问题（Traveling Saleman Problem，TSP） 又称为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。 整数规划问题；,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第21页,第1节：生产调度与优化,(5)常见的NP-难问题 装箱问题： 设有许多具有同样结构和负荷的箱子B1, B2, ，其数量足够供所达到目的之用。每个箱子的负荷（可为长度、重量等等.）为C，今有n个负荷为wj，0wjC，j=1,2,

17、n的物品 J1, J2, ,Jn需要装入箱内。装箱问题就是指寻找一种方法，使得能以最小数量的箱子数将J1, J2, ,Jn全部装入箱内。 哈密顿回路问题： 天文学家哈密顿(William Hamilton) 提出，在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第22页,第1节：生产调度与优化,(5)常见的NP-难问题 划分问题： 设有一整数集合A=a1,a2,an，如何将该集合划分为两个子集A1和A2，使得ajA1 aj= ajA2 aj =(ajA aj)/

18、2。 精确覆盖问题： 在一个全集X中若干子集的集合为S，精确覆盖(Exact cover)是指，S的子集S*，满足X中的每一个元素在S*中恰好出现一次。即满足条件： S*中任意两个集合没有交集，即X中的元素在S*中出现最多一次； S*中集合的全集为X，即X中的元素在S*中出现最少一次。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第23页,第1节：生产调度与优化,(6)优化模型的解决思路 多项式时间问题 步骤1.构造优化模型的多项式时间最优算法； 步骤2.证明上述算法所获得的解为该模型的最优解。 (强)NP-hard问题 思路1.启发式算法(启发式规则、近似

19、算法)； 思路2.精确算法(分枝定界算法、动态规划法等)； 思路3.亚启发式算法(模拟退火算法、遗传算法、禁忌搜索算法等)。 启发式算法必须针对具体问题特点构造相应的启发式规则。 精确算法和亚启发式算法具有通用框架。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第24页,第1节：生产调度与优化,(7)精确算法 分枝定界算法(B if ( n = 0 ) return 1; else temp= n * Factorial (n-1); return temp; ,规模减小,RetLoc2,附加内容：递归,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产

20、调度 2020年7月9日 第33页,Page 34,分析,分析：当调用函数时，系统为调用者构造一个由参数表和返回地址组成的活动记录（工作记录），并将其压入工作栈中，当有多个嵌套调用时，每调用一次产生一个工作记录，并依次压入工作栈中。当函数返回时，弹出栈顶记录。按照先调用后返回原则，将工作记录依次弹出。 对于递归调用，由于调用与被调函数是同一个函数，因此与调用相关的概念是“层次”。 工作记录：,附加内容：递归,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第34页,Page 35,分析,计算Factorial时活动记录的内容：,void main( ) long

21、 x; x=Factorial(4); ,栈顶,RetLoc2,附加内容：递归,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第35页,第1节：生产调度与优化,(8)亚启发式算法 对于NP-hard问题，传统的精确算法（分枝定界算法、动态规划算法等）仅能解决较小规模的问题，这是因为它们的空间复杂度或时间复杂度随着问题规模的变大而成指数型增长。据我们了解到的资料，关于生产调度中的许多NP-hard问题的分枝定界算法很少有能够处理规模大于100个作业的。 由于计算机软硬件技术的迅速发展，促使了局部搜索、模拟退火、可变邻域搜索、禁忌搜索、遗传算法等亚启发式算法的产生

22、。亚启发式算法通常基于搜索技术，通过对优化问题大规模解空间中的解搜索和比较，从而获得质量比较好的满意解。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第36页,第1节：生产调度与优化,(8)亚启发式算法 局部搜索(LS, Local Search)： 局部搜索(LS, Local Search)是一种在当前可行解的基础上，按照一定的方法产生邻域并以该邻域中的最优解作为下一个当前可行解的不断迭代的搜索算法，当算法无法改进某一当前可行解时则算法结束。对于优化问题而言，局部搜索是一种有效的搜索算法。首先，我们可以将一个优化问题表述为“对解向量x的不同参数寻找一组取

23、值，使得目标函数Z(x)最大化或最小化”。可见其本身就是一个搜索问题，其解空间是参数的不同组合。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第37页,第1节：生产调度与优化,(8)亚启发式算法 局部搜索算法框架： Step 1. 产生一个初始解x，对应目标函数值Z(x)； Step 2. 在解x的邻域里找最优邻居x; Step 3. 如果Z(x)Z(x)，则 x=x; Z(x)=Z(x); 转Step 2 ; Step 4. 返回解x和值Z(x)。结束。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第38页,第1节：生产

24、调度与优化,(8)亚启发式算法 局部搜索 优势在于： i)每一次循环迭代都占有恒定的内存需求； ii)它能够在非常大的解空间中进行寻优。 缺点在于： i)局部搜索仅能保证获得局部最优解，而无法断定该解全局最优； ii)解的质量可能会由于初始解的不同有一定的扰动。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第39页,第1节：生产调度与优化,(8)亚启发式算法 模拟退火(SA, Simulated Annealing)： 模拟退火是对局部搜索算法的一种拓展。 从某种意义上看，局部搜索之所以陷入局部最优陷阱是因为它每次迭代总是选择当前解邻域中的局部最优解。然而事

25、实上，一个全局最优解未必在某一当前局部最优解的邻域中。 模拟退火算法的思想是每次迭代算法以一定的概率接受劣解而不是永远选择邻域中的局部最优解。为了能使算法最终向全局最优解收敛，接受劣解的概率随迭代步数的增加而变小直至接近于0。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第40页,第1节：生产调度与优化,(8)亚启发式算法 模拟退火(SA, Simulated Annealing)： 模拟退火算法最早由Metropolis提出，并进而广泛用于解决大规模的复杂问题。模拟退火是算法思想来源于现实生活中金属物体的退火过程并因此称之为模拟退火。当金属物体温度比较高的

26、时候，分子运动比较剧烈，分子排列具有很大的随意性，此时物体具有比较高的能量级别；而当温度降低，分子运动变得缓慢并最终趋于稳定构成正方体的晶体矩阵，而此时物体的能量级别也达到最低。同样在模拟退火算法中，温度比较高时算法接受劣解的可能性比较大，温度较低时接受劣解的概率减小并最终趋于0，从而使得算法结束时优化问题的目标函数趋于最优。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第41页,第1节：生产调度与优化,(8)亚启发式算法 模拟退火算法框架： Step 1. 产生一个初始解x, 最优解x*=x；k=0; tk=tmax; Step 2. 若在该温度达到内循环

27、停止条件, 则转Step 3; 否则, 从邻域N(x)中随机选择一个解y ; 计算Z=Z(y)-Z(x); 若Z 0，则x*=y; 否则, 若exp(- Z/tk)random(0,1),则x*=y; 重复Step 2. Step 3. tk+1=d(tk); k=k+1; 若满足停止条件, 则返回解x和值Z(x), 结束。否则, 转Step 2.,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第42页,第1节：生产调度与优化,(8)亚启发式算法 可变邻域搜索(VNS, Variable Neighborhood Search)： 其原理是通过在搜索过程中不断

28、改变邻域结构而使得满意解不会陷入局部最优的陷阱。它也是对局部搜索的一种扩展，然而它与模拟退火算法避免陷入局部最优陷阱的机制却完全不同。可变邻域搜索认为局部搜索之所以陷入局部最优是因为其邻域构造方式不恰当并且仅采用一种邻域生成方法，因此要想获得全局最优解可以设计许多替补邻域生成方式，当第一种邻域生成方式陷入局部最优，可以转而采用第二种邻域生成方式改变搜索空间，直至采用所用的邻域生成方式均无法获得更优的解则算法结束。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第43页,第1节：生产调度与优化,(8)亚启发式算法 可变邻域搜索算法框架： 初始化: 设计一系列邻域

29、生成方法Nk(k=1,2,kmax);构造初始可行解x和结束条件； 当结束条件不满足, 循环如下步骤： I) k=1; II) 循环如下步骤，直到k=kmax; i)在x的第k个邻域中Nk随机生成一个邻居x; ii)寻找x邻域中的局部最优解x; iii)如果x优于x, 则x=x;k=1;继续在Nk中搜索, 否则k=k+1.,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第44页,第1节：生产调度与优化,(8)亚启发式算法 可变邻域搜索较常用变形VND： 初始化: 设计一系列邻域生成方法Nk(k=1,2,kmax);构造初始可行解x和结束条件； 当结束条件不满足

30、, 循环如下步骤： I) k=1; II) 循环如下步骤，直到k=kmax; i)在x的第k个邻域Nk中寻找局部最优解x; ii)如果x优于x, 则x=x ; 否则k=k+1.,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第45页,第2节：生产调度问题的符号表示与分类,(1)三参数表示法简介 自从1954年Johnson发表第一篇关于调度问题的研究文献以来，人们对调度问题产生了浓厚的兴趣。 相同的调度问题由于研究时间或研究人员所在研究领域的不同可能有不同的称谓，例如： 对于作业的到达时间，早期的文献一般称为准备时间(ready time)，而近期文献一般称为

31、释放时间(release date)；对于机器速度相同的平行机问题，排序引论称为同速机问题，而现代排序论称为同型机问题；对于机器速度不同且差异恒定的平行机问题，排序引论称为恒速机问题，而现代排序论称为同类机问题。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第46页,第2节：生产调度问题的符号表示与分类,(1)三参数表示法简介 现实中生产过程的复杂性造成了不同调度问题的约束条件与目标函数有很大差异。Graham提出的 三参数表示法能够较简单且清晰地描述一个具体的调度问题，并逐渐成为人们表示调度问题的标准形式。其中， 域用来表示与机器相关的一些信息； 域用于表

32、示与作业相关的一些信息； 域指示调度问题所要达到的目标。 例如，可以用符号Qm|rj|Cj来表示作业到达时间(释放时间)不同、目标是最小化完工时间和的同类机调度问题，其中，Qm表示同类机调度类型，rj表示作业具有到达时间(release date)的约束，Cj表示调度的目标是最小化完工时间和。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第47页,第2节：生产调度问题的符号表示与分类,(2)三参数表示法调度问题分类 根据域进行分类，可以将调度问题划分为单机问题、串行调度问题、并行调度问题以及混合调度问题。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生

33、产调度 2020年7月9日 第48页,第2节：生产调度问题的符号表示与分类,(2)三参数表示法调度问题分类 根据域中调度前所给作业信息的多少，可以将调度问题分为离线问题、在线问题。离线问题就是确定性的调度问题，即在调度之前已知作业的所有相关信息；在在线问题中，仅知道已到达作业的确切信息，而对尚未到达的作业一无所知。 域中常见的符号有：rj表示作业具有不同的到达时间；pmtn表示作业可以中断；prec表示作业有先后次序的限制；STsi表示作业之间有setup时间，但此setup时间与作业调度次序无关；STsd表示作业之间有setup时间，而且此setup时间与作业调度次序有关；Mj表示某些作业具

34、有可加工机器结合，而不能够在此集合之外的机器上加工。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第49页,第2节：生产调度问题的符号表示与分类,(2)三参数表示法调度问题分类 三参数表示法中的域用于指示调度的目标。 正则目标(Regular Performance Measures)和非正则目标。正则目标是指目标函数是作业完工时间的非减函数，而非正则目标则未必。常见的正则目标有：Cmax表示调度目标是最小化最大完工时间；Cj表示最小化完工时间和；wjCj表示最小化加权完工时间和；Lmax表示最小化最大延迟时间；Tj表示最小化延迟时间和；wjTj表示最小化加

35、权延迟时间和；Uj表示最小化误工作业个数；wjUj表示最小化加权误工作业个数。最常见的两个非正则目标是(Ej+Tj)和(wjEj+wjTj)，分别表示最小化提前/延迟时间和、最小化加权提前/延迟时间和，这两类调度问题研究的是及时交付的调度问题。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第50页,第3节：常见生产调度问题及其启发式规则,(1)常见调度参数回顾(作业信息中) 加工时间(Processing time)(pj) ： The amount of processing required by job j 释放时间(Release date) (rj

36、)： The time at which job j is available for processing 预交付时间(Due date) (dj)： The time at which the processing of job j is due to be completed,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第51页,第3节：常见生产调度问题及其启发式规则,(1)常见调度参数回顾(目标函数中) 完工时间(Completion time)(Cj): The time at which the processing of job j is fi

37、nished 工作流时间(Flowtime)(Fj): The time job j spends in the system: Fj = Cj rj 延迟时间(Lateness)(Lj): The amount of time by which the completion time of job j exceeds its due date: Lj = Cj dj 延迟时间(Tardiness)(Tj): The lateness of job j if it fails to meet its due date, or zero otherwise: Tj = max0, Lj,李凯(合

38、肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第52页,第3节：常见生产调度问题及其启发式规则,(2)常见目标函数,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第53页,第3节：常见生产调度问题及其启发式规则,(3)常见调度问题复杂性：多项式时间问题,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第54页,第3节：常见生产调度问题及其启发式规则,(3)常见调度问题复杂性：多项式时间问题,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第55页,第3节：常见生产调度问题

39、及其启发式规则,(3)常见调度问题复杂性：多项式时间问题,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第56页,第3节：常见生产调度问题及其启发式规则,(3)常见调度问题复杂性：NP-hard问题,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第57页,第3节：常见生产调度问题及其启发式规则,(3)常见调度问题复杂性：NP-hard问题,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第58页,第3节：常见生产调度问题及其启发式规则,(3)常见调度问题复杂性：NP-hard问题,李凯(合肥工业

40、大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第59页,第3节：常见生产调度问题及其启发式规则,(4)常见调度启发式规则 WSPT规则能够获得1|wjCj问题最优解。 WSPT(Weighted Shortest Processing Time first, 加权最短加工时间最短)。Total weighted flowtime (completion time) is minimized by SWPT sequencing (p1/w1 p2/w2 . . . pn/wn).,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第60页,第3

41、节：常见生产调度问题及其启发式规则,(4)常见调度启发式规则 SPT规则能够获得1|Cj问题最优解。 Smallest-Processing-Time (SPT) Rule. Whenever a machine is free for assignment, assign that job with the smallest processing time among all unassigned jobs. SPT规则能够获得Pm|Cj问题最优解。 例：3个机器，如下10个作业,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第61页,第3节：常见生产调度问

42、题及其启发式规则,(4)常见调度启发式规则 SRPT规则能够获得Pm|pmtn|Cj问题最优解。 Bakers Rule. At any moment of time, schedule that ready job with the smallest remaining processing time. 例： ERD规则能够获得1|rj|Cmax问题最优解。 ERD: Earliest Release Date first. (先来先服务),李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第62页,第3节：常见生产调度问题及其启发式规则,(4)常见调度启发式规

43、则 EDD规则能够获得1|Lmax问题、 1|rj,pj=1|Lmax问题最优解。 EDD: Earliest Due Date first. Step 1. 在当前到达的任务中，选取工期最小者加工（若有多个，任选其一）； Step 2. 每当加工完某任务，则转Step 1，重新确定当前加工任务，直到加工完全部任务。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第63页,第3节：常见生产调度问题及其启发式规则,(4)常见调度启发式规则 可中断的EDD规则能够获得1|rj,pmtn|Lmax问题最优解。 At any moment of time, sched

44、ule the job with the earliest due date.,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第64页,第3节：常见生产调度问题及其启发式规则,(4)常见调度启发式规则 大尾优先规则能够获得1|qj|Cmax问题最优解。 1|qj|Cmax问题等价于1|Lmax问题。 LDT: Largest Delivery Time first.,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第65页,第3节：常见生产调度问题及其启发式规则,(4)常见调度启发式规则 McNaughtons Wrap-Aro

45、und规则可以获得Pm|pmtn|Cmax问题最优解。 D=Cmax=maxpmax, (pj)/m McNaughtons Rule：Compute D. Assign the jobs in any order from time 0 until time D on machine 1. If a jobs processing extends beyond time D, preempt the job at time D, and compute its processing on machine 2, starting at time 0. Repeat this process u

46、ntil all jobs are assigned. (例如，两个机器，作业信息如下：),李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第66页,第3节：常见生产调度问题及其启发式规则,(4)常见调度启发式规则 Modified McNaughton规则可以获得Pm|pmtn|Cmax问题、 Pm|rj,pmtn|Cmax问题及其对应Online情形问题的最优解。 考虑了超长作业的调度 D=Cmax=maxpmax, (pj)/m Modified McNauthtons Rule：If pmax(pj)/m, then schedule the jobs

47、by McNaughtons wrap-around rule; otherwise schedule the longest job on one machine and delete the jobs from job set. (例如，两个机器，作业信息如下：),李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第67页,第3节：常见生产调度问题及其启发式规则,(4)常见调度启发式规则 SRPT-FM规则可以获得Qm|pmtn|Cj问题最优解。 SRPT-FM: Shortest Remaining Processing Time on the Fastes

48、t Machine rule.,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第68页,第3节：常见生产调度问题及其启发式规则,(4)常见调度启发式规则 P2|Cmax问题是NP-hard的。LPT规则的解收敛到Pm|Cmax问题最优解的(4/3-1/3m)倍以内。 例：m=3,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第69页,第4节：生产调度问题求解举例,(1)启发式规则构建举例 Qm|qj|Cmax问题的LPDT算法 Koulamas & Kyparisis (Scheduling on uniform parall

49、el machines to minimize maximum Lateness, Operations Research Letters, 2000,26:175-179.)论证了LDT(大尾优先)算法是(m-1)smax/si+1-近似算法。 例题：考虑2个均有11个机器的Qm|qj|Cmax问题。 问题1. s1=s2=s11=10。最坏误差界：1.91。 问题2. s1=10, s2=s3=s11=1。最坏误差界：6。 定理：假设在时刻，仅考虑作业J1和J2，p1+q1p2+q2，机器M1和M2均空闲，令s2=1，s1=k1。则： Cmax(J1M1,J2M2)Cmax(J1M2,J2

50、M1)。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第70页,第4节：生产调度问题求解举例,(1)启发式规则构建举例 Qm|qj|Cmax问题的LPDT算法 Step 1. 机器按照速度从大到小排列，各机器调度队列置空将作业队列中；所有作业按照长度与尾时间之和非增排序。 Step 2. 考虑作业队列队首作业，按照LDT规则预插入各机器子调度队列，指定Cmax最小的机器加工此作业(如果存在多个Cmax最小的机器，则现在慢机器)，将此作业从作业队列中删除。 Step 3. 如果作业队列空，结束；否则，转Step 2。,李凯(合肥工业大学管理学院) 生产运作管理

51、第5章：生产调度 2020年7月9日 第71页,第4节：生产调度问题求解举例,(1)启发式规则构建举例 Qm|qj|Cmax问题的LPDT算法 例：考虑如下 Qm|qj|Cmax 问题：有2个机器，s1=2，s2=1；3个作业长度分别为1、4、6，尾时间分别为3、2、1；则LDT调度结果Cmax=6.5，见图1-a；LPDT调度结果Cmax=6，见图1-b。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第72页,第4节：生产调度问题求解举例,(1)启发式规则构建举例 Qm|qj|Cmax问题的LPDT算法说明： I) LPDT算法仍然不能保证求得问题的最优解

52、。 II) 通过LPDT排序并依次为作业指定机器，通常能够获得较好的解，见例。这是因为LDT没有考虑到作业长度对调度结果的影响，特别是在机器速度有差别的同类机情形会降低调度结果的质量。 III) 将作业按照加工时间与尾时间之和非增排序可能会使得某些尾时间较大的作业考虑的时间较后，而且LDT能够使得问题中各机器调度队列排序最优，所以单纯使用LPDT规则未必能够保证各机器调度队列最优。在步骤2中，我们将某作业按照LDT规则预插入机器调度队列中，能够保证各机器调度队列最优。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第73页,第4节：生产调度问题求解举例,(1)

53、启发式规则构建举例 Qm|qj|Cmax问题的 LPDT算法 令： LB1为对应单机LDT值； LB2=max1jn(pj/s1+qj)。 LB=max(LB1,LB2)。,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第74页,(1)启发式规则构建举例 Qm|rj|Cj问题的HRS算法 （在提出此算法之前自己发表了相关论文，但结论不够完美！） 关于SPT和ERD无法使得Qm|rj|Cj问题获得比较好的解的思考： I) 当前作业后面会有多少作业？很难确定。 II)在同类机问题中一般假定s1 s2 sm，即优先考虑处理能力强的机器。将2个作业同时调度到不同机器上

54、时，应将长作业调度到速度快的机器，将短作业调度到速度慢的机器。 III) 另外，考虑2个等长但释放时间不同的作业调度到2个机器上，应将后释放的作业调度到速度快的机器上方能得到较好的调度结果。,第4节：生产调度问题求解举例,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第75页,(1)启发式规则构建举例 Qm|rj|Cj问题的HRS算法 Step 1. 将作业队列中所有作业按照LPT-LRD排序，即长作业优先，长度相同的作业后到达优先；各机器调度队列为空集； Step 2. 考虑作业队列首作业，将之预插入各机器调度队列，预插入时根据作业到达时间近可能靠近调度队列

55、的首部；选择完成时间和变化最小调度队列对应的机器加工此作业；将此作业从作业队列中删除； Step 3. 如果作业队列空，则结束；否则，转Step 2。,第4节：生产调度问题求解举例,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第76页,(1)启发式规则构建举例 Qm|rj|Cj问题的HRS算法 说明： I) HRS算法仍然不能保证求得问题的最优解，这是因为Qm|rj|Cj问题是强NP-hard问题，不可能存在多项式时间的最优算法； II) 通过LPT-LRD排序并依次为作业指定机器，使得为作业指定机器的过程中满足LPT和LRD规则； III) HRS算法优先

56、考虑长作业和后释放作业，但将作业预插入各机器调度队列中时尽量将其插到已考虑过作业的前面，因此，对于各机器上的调度队列仍然尽量满足SPT和ERD规则；,第4节：生产调度问题求解举例,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第77页,(1)启发式规则构建举例 Qm|rj|Cj问题的HRS算法 说明： IV) 由于所有作业按照LPT-LRD排序，因此相对于先考虑的作业，对于任意机器上的调度队列，尚未考虑的作业应具有更高的优先级。这样，在预插入一个作业时，能够较准确地计算出其对其后续作业完成时间及完成时间和的影响,第4节：生产调度问题求解举例,李凯(合肥工业大学

57、管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第78页,(1)启发式规则构建举例 Qm|rj|Cj问题的HRS算法,第4节：生产调度问题求解举例,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第79页,(2)亚启发式算法构建举例 Pm|Cmax问题的模拟退火算法 Pm|Cmax问题是一类常见的平行机调度问题，受到广大研究学者的关注。早期的文献一般基于一些启发式规则或加以改进。例如，Graham首先将LPT(Longest Processing Time first)规则应用到此问题；Coffman et al.根据装箱问题与最大完工时间问题的关

58、系，为Pm|Cmax问题提出了著名的MULTIFIT算法。虽然MULTIFIT算法不能保证严格优于LPT算法，但Friesen和Yue均证明了其最坏误差界优于LPT。另外一些算法则基于LPT或MULTIFIT进行改进以求得更高质量的解。 Lee W-C., Wu C-C., Chen P. A simulated annealing approach to makespan minimization on identical parallel machines. International Journal of Advanced Manufacturing Technology, 2006, 31:328-334,第4节：生产调度问题求解举例,李凯(合肥工业大学管理学院) 生产运作管理第5章：生产调度 2020年7月9日 第80页,(2)亚启发式算法构建举例 Pm|Cmax问题的模拟退火算法 SA-LWC算法的性能优于过去的启发式算法，然而，我们认为它存在着一些不足之处，其中最主要的是： SA-LWC算法仅采用交换邻域一种邻域生成方法，即交换不同处理机