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

李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第1页《生产运作管理》第5章生产调度李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第2页本章目录第1节：生产调度与优化第2节：生产调度问题的符号表示与分类第3节：常见生产调度问题及其启发式规则第4节：生产调度问题求解举例李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第3页第1节：生产调度与优化(1)调度问题举例生产调度属于企业的微观管理层次。企业在组织生产时必须充分考虑到企业内部人力、物力、财力以及企业外部供应链条件及国家法律对生态、环境保护的规定等多方面的约束，在此前提下尽可能利润最大化并提高客户满意度。企业生产过程中存在如下一类问题，主要研究如何充分利用企业内部的生产设备，尽可能提高客户满意度与企业利润，因此需要将待加工的任务或作业分配到一些机器上按照某种次序依次加工，这类问题统称为生产调度问题或排序问题。可见，生产调度旨在充分利用现有一定的资源，在满足一些必须条件的基础上，完成一定的任务并达到特定的调度目标，因此它本身就是一类典型的优化问题。李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第4页第1节：生产调度与优化(1)调度问题举例①一个车间要加工一批零件，每一个零件都具有相同的工序，即按照相同的顺序在几个不同的机床上加工。每个零件在每个机床上的加工时间可能不同。调度的目标是使得加工完所有零件的时间最短。这是一个流水线调度问题。②在汽车生产的焊装过程中，若干焊装工业机器人在尽量少的时间内完成一个整车3000多个焊点的焊装任务，最后一个焊点的焊装完成时间标志着所有焊装任务的完成，这就对应一个最小化最大完工时间的平行机调度问题。李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第5页第1节：生产调度与优化(1)调度问题举例对于这样一些生产调度问题，我们通常将机床、焊装工业机器人等抽象为机器(machine)；将零件、焊装点的焊装任务等抽象为作业(job)；调度问题的一个可行解是一个加工这些作业的序列；调度问题的最优解则是众多可行解中使得目标函数最优的可行解。生产调度问题是一类典型的优化问题，它旨在充分利用现有一定的资源，在满足一些必须条件的基础上，完成一定的任务并达到特定的调度目标。李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第6页第1节：生产调度与优化(1)调度问题举例--制造系统中的生产调度：李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第7页第1节：生产调度与优化(1)调度问题举例生产调度是为了实现生产计划的一个资源优化配置问题，是制造业系统中的一个重要环节。然而，调度问题远远不只是生产过程中的调度问题，它广泛存在于计算机系统、交通、医院、学校、服务业等。服务系统中的生产调度：李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第8页第1节：生产调度与优化(1)调度问题举例③一个大型超市共有50个收银台，每个收银台有一个收银员。每个收银员的收银速度（一个单位时间内平均扫描条形码的次数）相对恒定。目标是在尽量短的时间内满足更多用户的收银任务。由于收银员收银速度差异相对恒定，这是一个同类机调度问题。④某高校扩大招生数量，原来针对学生的网络服务器已远远不能满足学生的需要，为了提高网络服务质量，在原先网络服务器的基础上购置了1台新的服务器，并构建了由2台服务器组成的计算机机群（集群）系统。由于这2台服务器之间存在恒定的速度差异，这也是一个同类机调度问题。李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第9页第1节：生产调度与优化(2)调度问题是优化问题优化是研究如何充分利用时间、设备、成本、人力等有限的资源，达到某一或某些最优目标的理论，通常采用定量的研究方法。对于现实生产生活中的优化问题，通常需要为之建立相应的优化模型，从而避免问题定义的二义性，然后在此基础上设计一定的优化算法以获得问题的最优解或高质量满意解。因此，优化主要包括优化问题与优化方法两个方面，而优化问题一般采用优化模型来描述。李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第10页第1节：生产调度与优化(2)调度问题是优化问题由于优化模型是实际优化问题的数学描述，因此它也包括目标函数和约束条件两个部分。根据目标个数不同可以将优化问题分为单目标优化问题和多目标优化问题。一个单目标优化问题通常可以建立如下典型模型：，其中是全部解空间，S是解空间中满足约束条件的解的集合，而是S中的某一个解，被称为可行解。问题的目标是寻找一个最优解，使得。目标最大化的优化问题可以转化为目标最小化的形式。min{()|,}ZSSss瓮W**()(),ZZSsss??李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第11页第1节：生产调度与优化(2)调度问题是优化问题多目标优化问题的优化目标多于一个，可以建立如下形式的模型：，其中是一个非空集合，是一个函数向量，因此多目标优化又称为向量优化。多目标优化问题通常包含若干具有冲突的目标，因此往往难以保证所有目标同时达到最优。Pareto提出了Pareto最优解的概念，即针对某一决策变量无法找到与之更优的解。由于多目标优化问题具有若干个目标，因此通常具有众多的Pareto最优解，并形成Pareto最优集。nXR12()((),(),...,()):TnkfxfxfxfxXRmin{()|}fxxX李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第12页第1节：生产调度与优化(2)调度问题是优化问题由于现实生产生活中优化问题的复杂性和多样化，根据实际问题建立模型时约束条件及目标函数中的变量可能是确定型的或不确定型的，因此又可以将优化问题分为确定型优化问题和不确定型优化问题。对于不确定型优化问题，又可大致分为随机模型优化问题和模糊优化问题等。另外，根据解空间的特点还可以将优化问题分为连续型优化问题、离散型优化问题；根据决策变量的特点可以将优化问题分为线性优化问题、非线性优化问题等。李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第13页第1节：生产调度与优化(3)调度模型举例Pm||∑Cj问题的数学模型：李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第14页第1节：生产调度与优化(3)调度模型举例相同的问题，不同的模型：李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第15页第1节：生产调度与优化(3)调度模型举例更多的生产调度模型见《制造工程管理中的优化理论与方法》2.2节。①基于分配变量的模型②基于时间间隔的时序变量的模型③基于开始时间的时序变量的模型更复杂的调度模型，可以采用自然语言与数学符号相结合的方法进行描述。举例(见PDF文档)。李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第16页第1节：生产调度与优化(4)优化问题(模型)的复杂性首先看算法的“计算复杂性”，通俗说来，就是用计算机求解问题的难易程度。其度量标准：一是计算所需的步数或指令条数（这叫时间复杂度）；二是计算所需的存储单元数量（这叫空间复杂度）。时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。时间复杂度越来越受到重视。动态规划相关算法须关注空间复杂度。李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第17页第1节：生产调度与优化(4)优化问题(模型)的复杂性将计算问题按照在不同计算模型下所需资源的不同予以分类，从而得到一个对算法问题“难度”的类别，就是复杂性理论中复杂性类概念的来源。例如一个问题如果在确定性图灵机上所需时间不会超过一个确定的多项式(以输入的长度为多项式的不定元)，那么我们称这类问题的集合为P(polynomialtimeTuringmachine)。而将前述定义中的“确定性图灵机”改为“不确定性图灵机”，那么所得到的问题集合为NP(non-deteministicpolynomialtimeTuringmachine)。李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第18页第1节：生产调度与优化(4)优化问题(模型)的复杂性计算复杂性的初衷是理解不同算法问题的难度，特别的是一些重要算法问题的困难性。为了确切的描述一个问题的困难性，计算复杂性的第一步抽象是认为多项式时间是有效的，非多项式时间是困难的。这基于指数函数增长速度的“违反直觉”的特性：如果一个算法的时间复杂性为2n，取输入的规模是100，在运算速度是每秒1012（关于CPU速度，参见Instructionspersecond，其中报告截止2009年，主流个人电脑的运算速度可以看作是4*1010每秒）的情况下，该程序将会运行4*1010年，几乎是宇宙年龄。然而多项式的指数很大的时候，算法在实践中也不能看作是有效的。李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第19页第1节：生产调度与优化(4)优化问题(模型)的复杂性如果一个问题的复杂度是该问题的一个实例规模n的多项式函数，则这种可以在多项式时间内解决的问题属于P类问题。通俗地称所有复杂度为多项式时间的问题为易解的问题类，否则为难解的问题。简单的说，存在多项式时间的算法的一类问题，称之为P类问题；而像梵塔问题，推销员旅行问题等问题，至今没有找到多项式时间算法解的一类问题，称之为NP问题。同时，P类问题是NP问题的一个子集。多项式时间问题、NP-hard(NP难)问题、强NP-hard问题如果一个问题的特例是NP-hard的，则该问题也是NP-hard的。李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第20页第1节：生产调度与优化(5)常见的NP-难问题①背包问题：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。设有一个容积为b的背包，n个尺寸分别为ai、价值为ci的物品，如何装包使得总价值最大？(0-1背包问题)max∑1≤i≤ncixis.t.∑1≤i≤naixi≤b;xi∈{0,1},i=1,2,…,n李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第21页第1节：生产调度与优化(5)常见的NP-难问题②旅行商问题：旅行商问题（TravelingSalemanProblem，TSP）又称为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。③整数规划问题；李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第22页第1节：生产调度与优化(5)常见的NP-难问题④装箱问题：设有许多具有同样结构和负荷的箱子B1,B2,…，其数量足够供所达到目的之用。每个箱子的负荷（可为长度、重量等等.）为C，今有n个负荷为wj，0wjC，j=1,2,…,n的物品J1,J2,…,Jn需要装入箱内。装箱问题就是指寻找一种方法，使得能以最小数量的箱子数将J1,J2,…,Jn全部装入箱内。⑤哈密顿回路问题：天文学家哈密顿(WilliamHamilton)提出，在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿途恰好经过所有其他城市一次的路径。李凯(合肥工业大学管理学院)《生产运作管理》第5章：生产调度2020年3月11日第23页第