1、第十一章第十一章 制造业作业计划与控制制造业作业计划与控制 第一节第一节 排序问题的基本概念排序问题的基本概念第二节第二节 流水作业排序问题流水作业排序问题 第三节第三节 单件作业排序问题单件作业排序问题第四节第四节 生产作业控制生产作业控制第一节第一节 排序问题的基本概念排序问题的基本概念一、名词术语一、名词术语1编制作业计划（scheduling）：不仅包括确定工件的加工顺序，而且还包括确定机器加工每个工件的开始时间和完成时间。2排序（Sequencing）：只是确定工件在机器上的加工顺序。由于编制作业计划的主要问题是确定各台机器上工件的加工顺序，而且，在通常情况下都是按最早可能开（完）工
2、时间来编排作业计划的，因此，当工件的加工顺序确定之后，作业计划也就确定了。正因为如此，人们常常不加区别地使用“排序”与“编制作业计划”两个术语。3派工（Dispatching）:是按作业计划的要求，将具体生产任务安排到具体的机床上加工，属于我们经常说的“调度”范围。第一节第一节 排序问题的基本概念排序问题的基本概念一、名词术语一、名词术语 4赶工（Expediting）：是实际进度已落后于计划进度时采取的行动，也属于“调度”范围。5调度：是实行控制所采取的行动，是在加工制造发生之后的活动，是发现实际生产进度已经偏离预定计划而采取的调配资源的行动。调度的依据是作业计划。第一节第一节 排序问题的基
3、本概念排序问题的基本概念二、假设条件与符号说明（一）假设条件1.一个机器不能同时在几台不同的机器上加工。2.工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。3.不允许中断。当一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其它工作。4.每道只在一台机器上完成。5.工件数、机器数和加工时间已知，加工时间与加工顺序无关。6.每台机器同时只能加工一个工件。第一节第一节 排序问题的基本概念排序问题的基本概念第一节第一节 排序问题的基本概念排序问题的基本概念第一节第一节 排序问题的基本概念排序问题的基本概念三、排序问题的分类和表示法 （一）排序问题的表示法1按机器的
4、种类和数量不同 （1）单台机器的排序问题（不存在加工路线问题）（2）多台机器的排序问题 按工件加工路线的特征，可以将多台机器的排序问题分为：单件作业排序问题（工件的加工路线不同）流水作业排序问题（所有工件的加工路线完全相同）2按工件到达车间的情况不同 （1）静态的排序问题（进行排序时，所有工件都已到达，可以一次 对它们进行排序）第一节第一节 排序问题的基本概念排序问题的基本概念三、排序问题的分类和表示法（一）排序问题的表示法第一节第一节 排序问题的基本概念排序问题的基本概念 （二）排序问题的表示法 n/m/A/B 其中，n为工件数；m为机器数。A为车间类型，在A的位置以“F”表示，则代表流水作
5、业排序问题；若标以“P”，则表示流水作业排列排序问题；若标以“G”，则表示一般作业排序问题。当m1时，则A处为空白（单台机器的排序，无所谓加工路线）。B为目标函数，通常是其值最小。流水作业排列排序问题（P）是流水作业排序问题（F）的特殊情况。第二节第二节 流水作业排序问题流水作业排序问题 本节所讨论的是一种特殊情况，即所有工件本节所讨论的是一种特殊情况，即所有工件在各台机器上加工顺序都相同的情况。这就是排在各台机器上加工顺序都相同的情况。这就是排列排序问题。流水作业排列排序问题常被称作列排序问题。流水作业排列排序问题常被称作“同顺序同顺序”排序问题。排序问题。第二节第二节 流水作业排序问题流水
6、作业排序问题一、最长流程时间一、最长流程时间Fmaxmax的计算的计算 1讨论的类型属于n/m/P/Fmax 2目标函数：最长流程时间最短,Fmax最小。最长流程时间又称作加工周期，它是从第一个工件在第一台机器开始 加工时算起，到最后一个工件在最后一台机器上完成加工时为止所经过的时间。由于假设所有工件的到达时间都为零（ri=0,i=1,2，n）所以，Fmax等于排在末位加工的工件在车间的停留时间，也等于一批工件的最长完工时间Cmax，即Fmax=Cmax。推导：Fi=Ci-ri 又ri=o Fi=Ci 则Fmax=Cma 第二节第二节 流水作业排序问题流水作业排序问题一、最长流程时间一、最长流
7、程时间Fmaxmax的计算的计算 3、计算公式 （1）C1si=C1Si1+Psi1 Si在机器M1上的完工时间工件Si-1在机器M1上的完工时间工件Si在M1上的加工时间（3）Fmax=CmSn（工件Sn在机器Mm上的完工时间，即最后个工件在最后 一台机器上的完工时间）第二节第二节 流水作业排序问题流水作业排序问题 i 1 2 3 4 5 6 pi1 pi2 pi3 pi4 4 2 3 1 4 2 4 5 6 7 4 5 5 8 7 5 5 5 4 2 4 3 3 1第二节第二节 流水作业排序问题流水作业排序问题 i 6 1 5 2 4 3 pi1 pi2 pi3 pi4 2 2 46 41
8、0 212 113 316 57 411 415 520 727 633 512 517 522 830 535 742 113 421 325 232 338 446第二节第二节 流水作业排序问题流水作业排序问题二、二、n/2/n/2/F F/F Fmaxmax问题的最优算法问题的最优算法 S SM MJohnson Johnson 于于19541954年提出的算法。年提出的算法。JohnsonJohnson算法是建立在算法是建立在JohnsonJohnson法则法则的基础上。的基础上。JohnsonJohnson法则为：如果法则为：如果 min(amin(ai i b bj j)min(a
9、)b bi i的工件按的工件按b bi i值值不增不增的顺序排成一个序列的顺序排成一个序列B B（由大到小）（由大到小）；将将A A放在放在B B之前就构成一个最有加工顺序。之前就构成一个最有加工顺序。第二节第二节 流水作业排序问题流水作业排序问题 i 1 2 3 4 5 6 ai bi 5 1 8 5 3 4 7 2 2 4 7 4第二节第二节 流水作业排序问题流水作业排序问题三、一般三、一般n/m/p/Fmax问题的启发式算法问题的启发式算法mk 1第二节第二节 流水作业排序问题流水作业排序问题 i 1 2 3 4 pi1 Pi2 pi3 1 2 6 3 8 4 2 9 4 5 8 2 第
10、二节第二节 流水作业排序问题流水作业排序问题 2、关键工件法：、关键工件法：关键工件法是陈荣秋关键工件法是陈荣秋19831983年提出的一种启发式算法。步骤：年提出的一种启发式算法。步骤：（1 1）计算每个工件的总加工时间）计算每个工件的总加工时间Pi ip pijij，找出加工时间最长的，找出加工时间最长的 工件工件C C（j jm m），将其作为关键工件。），将其作为关键工件。（2 2）对余下的工件，若对余下的工件，若p pi1i1ppimim，则按，则按p pi1i1不减（由小到大）不减（由小到大）的顺序排的顺序排 成一个序列成一个序列S Sa a；若；若p pi1i1ppimim，则按
11、，则按p pimim不增（由大到小）不增（由大到小）的顺序排成的顺序排成 一个序列一个序列S Sb b。（3 3）顺序（）顺序（S Sa a，C C，S Sb b）即为所求顺序。）即为所求顺序。第二节第二节 流水作业排序问题流水作业排序问题 i 1 2 3 4 pi1 Pi2 pi3 pi 1 2 6 3 8 4 2 9 4 5 8 2 13 11 16 14 2、关键工件法：、关键工件法：第二节第二节 流水作业排序问题流水作业排序问题 3、CDS法：法：Campbell,DudekCampbell,Dudek,Smith,Smith三人提出的一种启发式算法，简称三人提出的一种启发式算法，简称
12、CDSCDS法。法。具体做法：具体做法：对加工时间对加工时间 和和 用用Johnson算法求（算法求（m-1）次加工顺序，取其中最好的结果。）次加工顺序，取其中最好的结果。（l=1,2,m-1），），lkikp1mlmkikp1第二节第二节 流水作业排序问题流水作业排序问题 i 1 2 3 4l1 pi1 1 2 6 3 pi3 4 5 8 2l2 Pi1 Pi2 9 6 8 12 Pi2 pi3 12 9 10 113、CDS法：法：第三节第三节 单件作业排序问题单件作业排序问题第三节第三节 单件作业排序问题单件作业排序问题第三节第三节 单件作业排序问题单件作业排序问题第三节第三节 单件作业
13、排序问题单件作业排序问题 t Ot Tk Tk T*M*Oj 1 1,1,1 2,1,3 0 0 2 3 2 M1 1,1,1 2 1,2,3 2,1,3 2 0 6 3 3 M3 2,1,3 3 1,2,3 2,2,1 3 3 7 7 7 M3 M1 1,2,3 4 1,3,2 2,2,1 7 3 8 7 7 M1 2,2,1 5 1,3,2 2,3,2 7 7 8 12 8 M2 1,3,2 6 2,3,2 8 13 13 M2 2,3,2第三节第三节 单件作业排序问题单件作业排序问题第三节第三节 单件作业排序问题单件作业排序问题 t Ot Tk Tk T*M*Oj 1 1,1,1 2,1
14、,3 0 0 2 3 0 0 M1 M3 1,1,1 2 1,2,3 2,1,3 2 0 6 3 0 M3 2,1,3 3 1,2,3 2,2,1 3 3 7 7 3 3 M3 M1 1,2,3 4 1,3,2 2,2,1 7 3 8 7 3 M1 2,2,1 5 1,3,2 2,3,2 7 7 8 12 7 7 M2 M2 2,3,2 6 1,3,2 12 13 12 M2 1,3,2第三节第三节 单件作业排序问题单件作业排序问题 优先调度法则优先调度法则内内 容容特特 点点（1）SPT法则：法则：优先选择加工时间最短的工序；优先选择加工时间最短的工序；可使工件的平均流程时间最可使工件的平均
15、流程时间最短，减少在制品量短，减少在制品量（2）FCFS法则：法则：优先选择最早进入可排工序集合的优先选择最早进入可排工序集合的工件；工件；来自排队论，它对工件较公来自排队论，它对工件较公平平（3）EDD法则：法则：优先选择完工期限紧的工件（优先选择完工期限紧的工件（di）可使工件最大延误时间最小。可使工件最大延误时间最小。（4）MWKR法则：法则：优先选择余下加工时间最长的工件；优先选择余下加工时间最长的工件；使不同工作量的工件的完工使不同工作量的工件的完工时间尽量接近时间尽量接近（5）LWKR法则：法则：优先选择余下加工时间最短的工件；优先选择余下加工时间最短的工件；使工作量小的工件尽快完
16、成使工作量小的工件尽快完成（6）MOPNR法则：法则：优先选择余下工序数最多的工件；优先选择余下工序数最多的工件；与与MWKR法则类似，只不法则类似，只不过考虑工件在不同机器上的过考虑工件在不同机器上的转运排队时间是主要的。转运排队时间是主要的。（7）SCR法则：法则：优先选择临界比最小的工件（临界优先选择临界比最小的工件（临界比为工序允许停留的时间（比为工序允许停留的时间（ai）与）与工件余下加工时间之比）工件余下加工时间之比）保证工件延误最少保证工件延误最少（8）RANDOM法法则：则：随机地挑选一个工件随机地挑选一个工件 第三节第三节 单件作业排序问题单件作业排序问题第四节第四节 生产作
17、业控制生产作业控制第四节第四节 生产作业控制生产作业控制二、不同生产类型生产控制的特点（一）单件小批生产1单件小批生产主要特点（1）产品品种千差万别，零件种类繁多；（2）每个零件都有其特定的加工路线，整个物流没有什么主流；（3）各种零件都在不同的机器前面排队等待加工；（4）各个工作地之间的联系不是固定的。2工件的生产提前期（1）移动时间：取决于运输工具和运输距离，相对稳定；（2）排队时间：单个工件的排队时间是优先权的函数，所有工件的 平均排队时间与计划调度的水平有关；（3）调整准备时间：与技术和现场组织管理水平有关；（4）加工时间：取决于采用的加工技术和工人的熟练程度，它与计划 调度方法无关；（5）等待运输时间：与计划调度工作有关。第四节第四节 生产作业控制生产作业控制 3生产控制的重点（解决的主要问题）控制排队的队长控制排队时间（排队时间越长，在制品库存 就越高）；控制方法：输入/输出控制；二、不同生产类型生产控制的特点（一）单件小批生产
