运营管理排序和控制

1、Operations Management第七章综合生产计划第七章综合生产计划第九章第九章作业排序和控制作业排序和控制 Operations ManagementOperations Management第七章综合生产计划第七章综合生产计划（1）了解作业排序的含义）了解作业排序的含义（2）掌握流水线作业的基本模型，）掌握流水线作业的基本模型， 成批加工成批加工零件的移动顺序零件的移动顺序（3）掌握生产作业控制内容和方法）掌握生产作业控制内容和方法学习目标学习目标主要内容主要内容9.1 排序的基本概念排序的基本概念9.2 流水作业排序问题流水作业排序问题9.3 生产作业控制生产作业控制Opera

2、tions Management第七章综合生产计划第七章综合生产计划9.1 排序的基本概念排序的基本概念术语术语排序：确定工件在机床（工作地，服务台）上的加工排序：确定工件在机床（工作地，服务台）上的加工（服务）顺序。（服务）顺序。A工序工序工件工件B工序工序C工序工序D工序工序E工序工序确定谁先谁后确定谁先谁后我先我先！我先我先！Operations Management第七章综合生产计划第七章综合生产计划9.1 排序的基本概念排序的基本概念术语术语派工：按作业计划要求，将具体生产任务安排到具体派工：按作业计划要求，将具体生产任务安排到具体的机床上加工。的机床上加工。赶工：实际进度落后于计划

3、进度采取的行动。赶工：实际进度落后于计划进度采取的行动。调度：运营过程的现场指挥。调度：运营过程的现场指挥。编制作业计划（车间，工段）：确定工件的加工顺序，编制作业计划（车间，工段）：确定工件的加工顺序，以及确定机床加工每个工件的开始时间和完成时间。以及确定机床加工每个工件的开始时间和完成时间。注意：编制作业计划和排序的关系注意：编制作业计划和排序的关系Operations Management第七章综合生产计划第七章综合生产计划9.1 排序的基本概念排序的基本概念假设条件假设条件一个工件不能同时在几台不同的机器上加工一个工件不能同时在几台不同的机器上加工工件采取平行移动方式工件采取平行移动方

4、式连续加工，一个工件开始加工必须一直进行到完工，连续加工，一个工件开始加工必须一直进行到完工，不得中途停止（工序间和工序内）不得中途停止（工序间和工序内）每到工序只在一台机器上完成每到工序只在一台机器上完成工件数、机器数、加工路线和工件在每工序（机器）工件数、机器数、加工路线和工件在每工序（机器）的加工时间确定，工件在每工序（机器）的加工时间的加工时间确定，工件在每工序（机器）的加工时间与加工顺序无关。与加工顺序无关。每台机器同时只能加工一个工件每台机器同时只能加工一个工件Operations Management第七章综合生产计划第七章综合生产计划9.1 排序的基本概念排序的基本概念符号说明

5、符号说明Ji为工件为工件i，i=1,2,3，nMj为机器为机器j，j=1,2,3，mpij为为Ji工件在工件在Mj机器上的加工时间，机器上的加工时间，Ji的总加工时间为的总加工时间为Pi，wij为为Ji工件在工件在Mj机器的等待加工时间或运输时间（延迟加工时间），机器的等待加工时间或运输时间（延迟加工时间），Wi为为Ji工件总延迟加工时间，工件总延迟加工时间，ri为为Ji的到达时间，指的到达时间，指Ji从外部进入加工地（车间或机器），可以开从外部进入加工地（车间或机器），可以开始加工的最早时间始加工的最早时间di为为Ji的完工期限的完工期限Ci为为Ji的完工时间，的完工时间，Cmax为最长完工

6、时间，为最长完工时间，Cmax=maxCi（ i=1,2,3，n）kjiji pP1kjiiiijijiiPWrpwrC1）（kjijiwW1Operations Management第七章综合生产计划第七章综合生产计划9.1 排序的基本概念排序的基本概念符号说明符号说明Fi为为Ji的流程时间（在车间的实际停留时间），的流程时间（在车间的实际停留时间），Fi = Ciri = Wi+PiFmax为最长流程时间，为最长流程时间， Fmax=maxFiLi为工件的延迟时间。为工件的延迟时间。Li0（正延迟，（正延迟，Ji工件实际完工时间超过了完工期限）；工件实际完工时间超过了完工期限）； Li0（

7、负延迟，（负延迟，Ji工件实际完工时间早于完工期限）；工件实际完工时间早于完工期限）； Li = 0 （零延迟，（零延迟，Ji工件实际完工时间等于完工期限）工件实际完工时间等于完工期限）Lmax为最长延迟时间为最长延迟时间，Lmax= maxLi （ i =1,2,3，n）iiiiiiiiiiiiia-Fr -d-WPd-WPrd-CL）（）（Operations Management第七章综合生产计划第七章综合生产计划9.1 排序的基本概念排序的基本概念排序问题分类排序问题分类单台机器排序单台机器排序多台机器排序多台机器排序排序问题排序问题机器的种类和数量机器的种类和数量单件作业排序单件作业

8、排序（job-shop）流水作业排序流水作业排序（flow-shop）工件加工线路工件加工线路静态排序问题静态排序问题动态排序问题动态排序问题排序问题排序问题工件到达加工地情况工件到达加工地情况确定型排序问题确定型排序问题随机型排序问题随机型排序问题排序问题排序问题参数性质参数性质平均流程时间最短平均流程时间最短误期完工工件数最少误期完工工件数最少排序问题排序问题目标函数性质目标函数性质多目标排序多目标排序单目标排序单目标排序目标函数数量目标函数数量Operations Management第七章综合生产计划第七章综合生产计划9.1 排序的基本概念排序的基本概念排序表示法（康威法排序表示法（康

9、威法Conway）n / m / A / B工件数工件数机器数机器数作业类型：作业类型：F和和p流水线，流水线，G单件单件目标函数目标函数6/8/p/Fmax？10/5/G/Cmax？Operations Management第七章综合生产计划第七章综合生产计划9.2 流水作业排序流水作业排序注意两个顺序注意两个顺序不同工件的加工工艺决定的在不同机器之间的加工先后顺序不同工件的加工工艺决定的在不同机器之间的加工先后顺序加工加工工艺顺序工艺顺序不同工件在同一台机器上的加工先后顺序不同工件在同一台机器上的加工先后顺序-加工顺序加工顺序（假设不同工（假设不同工件在每一台机器上的加工先后顺序相同）件在

10、每一台机器上的加工先后顺序相同）机器机器A机器机器B机器机器C机器机器D加工顺序加工顺序1-3-2加工顺序加工顺序1-3-2加工顺序加工顺序1-3-2加工顺序加工顺序1-3-2加工工艺顺序加工工艺顺序A-B-C-DOperations Management第七章综合生产计划第七章综合生产计划9.2 流水作业排序流水作业排序最长流程时间最长流程时间Fmax的计算的计算n/m/p/Fmax问题，目标函数是最长流程时间（加工周期）最短问题，目标函数是最长流程时间（加工周期）最短因为：因为：ri=0，所以：，所以： Fmax= Cmax设：设：n个工件的加工顺序为个工件的加工顺序为S =（S1、S2、

11、S3、Sn），其中），其中Si为为排在排在i位加工的工件代号。位加工的工件代号。Cksi表示工件表示工件Si在机器在机器Mk上的完工时间，上的完工时间，pksi表示工件表示工件Si在机器在机器Mk上的加工时间。上的加工时间。机器数：机器数：k=1，2，3，4，m；工件数：；工件数：i=1，2，3，n递推计算公式：递推计算公式：（1）C1si=C1（si-1）+psi1（Si工件在机器工件在机器1的完工时间）的完工时间）（2）Cks1=C（k-1）1+ps1k（S1工件在机器工件在机器k的完工时间）的完工时间）（3）Cksi=maxC（k-1）si，Ck（si-1）+psik其中：其中：k=2，

12、3，4，m；工件数：；工件数：i=2，3，nFmax= ri+Cmsn当当ri = 0时，时， Fmax= Cmsn（最后加工工件（最后加工工件n在最后机器在最后机器m的完工时间）的完工时间）Operations Management第七章综合生产计划第七章综合生产计划9.2 流水作业排序流水作业排序最长流程时间最长流程时间Fmax的计算的计算例：有一个例：有一个6/4/p/Fmax问题，其加工时间如表所示。当按顺序问题，其加工时间如表所示。当按顺序S=（6,1,5,2,4,3）加工时，求）加工时，求 Fmax=？i123456psi1442639110414216psi24851361972

13、6430535psi3513821728533538543psi4417223432336341144加工时间矩阵（加工时间矩阵（1,2,3,4,5,6）机器（顺序由技术工艺要求决定）机器（顺序由技术工艺要求决定）工件加工先后顺序工件加工先后顺序Operations Management第七章综合生产计划第七章综合生产计划9.2 流水作业排序流水作业排序最长流程时间最长流程时间Fmax的计算的计算i615243psi12246410212113316psi257411415520727633psi3512517522830535742psi4113421325232338446加工时间矩阵（加

14、工时间矩阵（6,1,5,2,4,3）机器（顺序由技术工艺要求决定）机器（顺序由技术工艺要求决定）工件加工先后顺序工件加工先后顺序结论：工件加工先后顺序（排序）不同，结论：工件加工先后顺序（排序）不同， Fmax也不同。也不同。Operations Management第七章综合生产计划第七章综合生产计划9.2 流水作业排序流水作业排序n/2/F/Fmax问题的最优算法问题的最优算法Johnson法则（法则（S.M.Johnson，1954年）年）ai表示工件表示工件Ji在机器在机器M1上的加工时间，上的加工时间，bi表示工件表示工件Ji在机器在机器M2上的上的加工时间，每个工件加工工艺线路相同

15、：加工时间，每个工件加工工艺线路相同：M1M2如果：如果：min（ai，bj）min（aj，bi），则工件），则工件Ji排在排在Jj之前；如果之前；如果min（ai，bj）= min（aj，bi），则工件），则工件Ji和和Jj之间任意顺序。之间任意顺序。（i、j为两两比较的工件号）为两两比较的工件号）Johnson算法算法（1）从加工时间矩阵中找出最短加工时间）从加工时间矩阵中找出最短加工时间（2）若最短加工时间出现在）若最短加工时间出现在M1上，则对应的工件尽量往前排；若上，则对应的工件尽量往前排；若最短加工时间出现在最短加工时间出现在M2上，则对应工件尽可能往后排。如最短加上，则对应工件尽

16、可能往后排。如最短加工时间有多个，则任选一个。工时间有多个，则任选一个。（3）在加工时间矩阵中划去已排序的工件，剩余工件重复上述过）在加工时间矩阵中划去已排序的工件，剩余工件重复上述过程至所有工件完成排序。程至所有工件完成排序。Operations Management第七章综合生产计划第七章综合生产计划9.2 流水作业排序流水作业排序n/2/F/Fmax问题的最优算法问题的最优算法Johnson改进算法改进算法（1）将所有）将所有aibi的工件按的工件按ai值不减的顺序排成一个加工顺序值不减的顺序排成一个加工顺序A。（2）将所有）将所有aibi的工件按的工件按bi值不增的顺序排成一个加工顺序

17、值不增的顺序排成一个加工顺序B。（3）最优加工顺序：）最优加工顺序：A+B一般一般n/mP/Fmax问题的启发式算法（近优解）问题的启发式算法（近优解）Palmer法（法（D.S.Palmer ，1965年）年）按斜度指标（按斜度指标（l l i）排列工件加工顺序）排列工件加工顺序（1）计算工件斜度指标：）计算工件斜度指标：（2）按各工件）按各工件l l i不增的顺序排列工件。不增的顺序排列工件。符号含义：符号含义：m为机器数，为机器数，pik为工件为工件i在机器在机器Mk上的加工时间。上的加工时间。ikmkip/mk-121 ）（k=1,2，nOperations Management第七章

18、综合生产计划第七章综合生产计划9.2 流水作业排序流水作业排序一般一般n/mP/Fmax问题的启发式算法（近优解）问题的启发式算法（近优解）关键工件法（关键工件法（D.S.Palmer ，1965年）年）（1）计算每个工件的总加工时间：）计算每个工件的总加工时间：（2）选择加工时间最长的工件作为关键工件）选择加工时间最长的工件作为关键工件C。（3）对于余下的工件，将所有工件在）对于余下的工件，将所有工件在M1机器上的时间胡和机器上的时间胡和Mm机机器上的时间比较。如器上的时间比较。如pi1pim，则按，则按pi1不减的顺序排成一个序列不减的顺序排成一个序列Sa；如如pi1pim，则按，则按pi

19、m不增的顺序排成一个序列不增的顺序排成一个序列Sb。（4）顺序（）顺序（Sa，C，Sb）为近优解。）为近优解。CDS法（法（Campbell-Dudek-Smith）Johnson算法在一般算法在一般n/mP/Fmax问题的应用问题的应用（1）将）将m台机器转化成台机器转化成m-1个个n/2/F/Fmax问题，形成的问题，形成的n/2/F/Fmax问题的加工时间为：问题的加工时间为：ijmjipP 1iklkp 1ikm-lmkp 1和和1.21m-，,l 其中：Operations Management第七章综合生产计划第七章综合生产计划9.2 流水作业排序流水作业排序一般一般n/mP/Fm

20、ax问题的启发式算法（近优解）问题的启发式算法（近优解）CDS法（法（Campbell-Dudek-Smith）（2） 用用Johnson算法得出（算法得出（m-1）个加工顺序，取其中最好结果。）个加工顺序，取其中最好结果。例：有一个例：有一个6/4/p/Fmax问题，其加工时间矩阵如下所示。用问题，其加工时间矩阵如下所示。用CDS法法求解最优顺序。求解最优顺序。i123456pi1423142pi2456745pi3587555pi4424331Operations Management第七章综合生产计划第七章综合生产计划9.2 流水作业排序流水作业排序一般一般n/mP/Fmax问题的启发式

21、算法（近优解）问题的启发式算法（近优解）CDS法（法（Campbell-Dudek-Smith）（1）求解：）求解：得出两个机器工件加工时间组合方式：得出两个机器工件加工时间组合方式：l =1时为（时为（pi1，pi4）；）；l =2时为（时为（pi1+ pi2 ，pi3+ pi4）；）；l =3时为（时为（pi1+ pi2 +pi3 ，pi2 + pi3 + pi4）iklkp 1ikm-lmkp 1和和321，,l ：其中l组合方式组合方式123456l =1pi1423142pi4424331l =2pi1+ pi2879887pi3+ pi491011886l =3pi1+ pi2 +

22、pi3131516131312pi2 + pi3 + pi4131517151211Operations Management第七章综合生产计划第七章综合生产计划9.2 流水作业排序流水作业排序一般一般n/mP/Fmax问题的启发式算法（近优解）问题的启发式算法（近优解）（2）用）用Johnson算法得出：算法得出：l =1近优解为（近优解为（4，2，3，1，5，6）；）； l =2近优解为（近优解为（2，1，4，5，3，6）；）； l =3近优解为（近优解为（1，4，2，3，5，6）（3）分别计算近优排序的）分别计算近优排序的Fmax，选择选择Min（ Fmax）的排序。的排序。Operat

23、ions Management第七章综合生产计划第七章综合生产计划9.2 流水作业排序流水作业排序相同工件、不同移动方式下加工周期的计算相同工件、不同移动方式下加工周期的计算工件移动方式指工件在生产过程中的运送组织方式问题。工件移动方式指工件在生产过程中的运送组织方式问题。移动方式：移动方式：顺序移动、平行移动和平行顺序移动顺序移动、平行移动和平行顺序移动顺序移动方式顺序移动方式:整批移动。例见教材整批移动。例见教材P306为工序数目。工序单件工序时间；为工件在第为工件加工批量；其中：顺mitntTimii， 1工序工序T顺顺时间时间020406080100120140160M1M2M3M4t

24、1t2t3t4Operations Management第七章综合生产计划第七章综合生产计划9.2 流水作业排序流水作业排序平行移动方式平行移动方式:单件立即移动。例见教材单件立即移动。例见教材P307为最长单件工序时间。其中：平LLmiittn-tT，）（ 11T平平工序工序时间时间020406080100120140160M1M2M3M4t1t2t3t4Operations Management第七章综合生产计划第七章综合生产计划9.2 流水作业排序流水作业排序平行顺序移动方式：平行顺序移动方式：（1）titi+1，工件按平行移动方式转移；，工件按平行移动方式转移； titi+1，以以i工

25、序最后一个零件的完工时间为基准，往前推移（工序最后一个零件的完工时间为基准，往前推移（n-1） ti+1作作为工件在（为工件在（i+1）工序开始时间）工序开始时间。例见教材。例见教材P307-308 1111min1miiimii，ttn-tnT）（）（平顺T平顺平顺工序工序时间时间020406080100120140160M1M2M3M4t1t2t3t4Operations Management第七章综合生产计划第七章综合生产计划9.2 流水作业排序流水作业排序平行顺序移动方式：平行顺序移动方式：各工序作业开始时间各工序作业开始时间T平顺平顺工序工序时间时间020406080100120140160M1M2M3M4t1t2t3t4），（，（1