生产第十一章

第十一章制造业作业计划与控制第一节作业计划问题的基本概念第二节流水作业排序问题第三节单件作业排序问题本章结构1.1基本概念第一节作业计划问题的基本概念编制作业计划或日程安排排序派工控制赶工调度机器零件1.2假设条件与符号说明（1）假设条件：一个工件不能同时在几台不同的机器上加工；工件在加工过程中采取平行移动方式；不允许中断；每道工序只在一台机器上完成；工件数、机器数和加工时间已知，加工时间与加工顺序无关；每台机器同时只能加工一个工件。（2）部分符号：Ji——工件i，i＝1，2，…，nMj——机器j，j＝1，2，…，mpij——Ji在Mj上的加工时间，Ji的总加工时间为Pi＝ΣpijCmax——最长完工时间，Cmax＝max{Ci}Fmax——最长流程时间，Fmax＝max{Fi}Lmax——最长延迟时间，Lmax＝max{Li}1.3排序问题的分类和表示法（1）排序问题的分类：按行业分：制造业的作业排序服务业的作业排序按机器种类和数量不同分：单机排序多机排序多机排序又按加工路线的特征分为：单件作业排序和流水作业排序问题。（2）表示法：康威用4个参数的排序问题表示法：n/m/A/Bn：工件数；m：机器数；A：车间类型，有“F”类，“P”类，“G”类等。【F表示流水作业排序问题；P表示流水作业排列排序问题；G表示一般单件作业排序问题】；B：目标函数，通常是使其值最小。第二节流水作业排序问题（1）流水作业排序问题的基本特征:是每个工件的加工路线都一致。前置内容:（2）流水作业的排序问题主要包括：最长流程时间的计算;两台机器排序问题的最优算法;多台机器排序问题的启发式算法;相同零件、不同移动方式下加工周期的计算。2.1最长流程时间Fmax的计算例1：有一个6/4/p/Fmax问题，其加工时间如下表，当按顺序S＝（6，1，5，2，4，3）加工时，求Fmax。表2.1加工时间矩阵i123456Pi1423142Pi2456745Pi3587555Pi4424331解法：按所求顺序列出加工时间矩阵；将每个工件的完工时间标在其加工时间的右上角；最后一个工件在最后一台机器上的完工时间即是最长流程时间Fmax。2.2n/2/F/Fmax问题的最优算法（两台机器流水作业排序）例2：求下表所示的6/2/F/Fmax问题的最优解。i123456ai518534bi722474表2.2加工时间矩阵解法（约翰森算法）：从加工时间矩阵中找出最短加工时间；若最短加工时间出现在机器M1上，则对应工件应该尽可能往前排；若最短加工时间出现在机器M2上，则对应工件应该尽可能往后排。然后从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个，则任挑一个。若所有工件都已排序，停止。否则，转步骤（1）。2.3一般n/m/P/Fmax问题的启发式算法(多台机器排列排序)（1）Palmer法（帕尔玛法）工件的斜度:i例3:i1234Pi11263Pi28429Pi34582表2.3加工时间矩阵有一个4/3/F/Fmax问题，其加工时间如下表所示，用（Palmer）法求解。（2）关键工件法计算每个工件的总加工时间，将加工时间最长的工件作为关键工件C；对于余下的工件，若pi1≤pim则按pi1不减的顺序排成一个序列Sa,若pi1pim则按pim不增的顺序排成一个序列Sb;顺序（Sa,C,Sb）即为所求顺序。有一个4/3/F/Fmax问题，其加工时间如下表所示，用关键工件法求解。例4:表2.4加工时间矩阵i1234Pi11263Pi28429Pi34582pi13111614（3）CDS法例5:有一个4/3/F/Fmax问题，其加工时间如下表所示，用CDS法求解。i1234Pi11263Pi28429Pi34582表2.5加工时间矩阵表2.6用CDS法求解i1234l=1Pi11263Pi34582l=2Pi1+Pi296812Pi2+Pi312910112.4相同零件不同移动方式下加工周期的计算零件在加工过程中的三种典型移动方式：顺序移动方式平行移动方式平行顺序移动方式（1）顺序移动方式102030405060708090100110n=4t1=8分钟t2=4分钟t3=10分钟t4=6分钟TOt1t2t3t1图6-3顺序移动方式时间(分钟)1式中：T顺:顺序移动方式的加工周期；n:零件加工批量；ti:第i道工序的单件工时；m:零件加工的工序数目。miitnT1顺（2）平行移动方式102030405060n=4t1=8分钟t2=4分钟t3=10分钟t4=6分钟TP图6-4平行移动方式时间(分钟)2tL——最长的单件工序时间。LmiitntT)1(1平（3）平行顺序移动方式10203040506070n=4t1=8分钟t2=4分钟t3=10分钟t4=6分钟TPO图6-5平行顺序移动方式时间(分钟)3特点：既要求每道工序连续进行加工，又要求各道工序尽可能平行地加工。其具体做法：当ti＜ti+1时，零件按平行移动方式移动；当ti≥ti+1时，以i工序最后一个零件的完工时间为基准，往前推移（n-1）×ti+1作为零件在i+1工序的开始加工时间。1111(1)min(,)mmijjijTntntt平顺第三节单件作业排序问题3.1问题的描述加工描述矩阵和加工时间矩阵1,1,11,2,31,3,22,1,32,2,12,3,2D=241345T=3.2两种作业计划的构成单件作业排序问题中，有2个重要的作业计划:能动作业计划;无延迟作业计划。（1）能动作业计划的构成符号说明：每安排一道工序称为一“步”；{St}:t步之前已排序工序构成的部分作业计划；{Ot}:t步可排序工序的集合；Tk:为{Ot}中工序Ok的最早可能开始时间；T’k:为{Ot}中工序Ok的最早可能完成时间。例5：有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T分别为：1,1,11,2,31,3,22,1,32,2,12,3,2D=241345T=试：构成一个能动作业计划？t{Ot}TkT`kT*M*Oj11,1,12,1,300232M11,1,121,2,32,1,320633M32,1,331,2,32,2,133777M3M11,2,341,3,22,2,173877M12,2,151,3,22,3,2778128M21,3,262,3,281313M22,3,2表3.1能动作业计划的构成26能动作业计划的甘特图2,3,21,1,12,2,11,3,22,1,31,2,33778132370时间机器M1M2M3（2）无延迟作业计划的构成例6：有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T分别为：1,1,11,2,31,3,22,1,32,2,12,3,2D=241345T=试：构成一个无延迟作业计划？t{Ot}TkT`kT*M*Oj11,1,12,1,3002300M1M31,1,121,2,32,1,320630M32,1,331,2,32,2,1337733M3M11,2,341,3,22,2,173873M12,2,151,3,22,3,27781277M2M22,3,261,3,2121312M21,3,2表3.2无延迟作业计划的构成29无延迟作业计划的甘特图2,3,21,1,12,2,12,1,31,2,337712132370时间机器M1M2M31,3,23.3三类启发式算法优先调度法则随机抽样法概率调度法