作业计划(排序)-生产计划与控制

《作业计划(排序)-生产计划与控制》由会员分享，可在线阅读，更多相关《作业计划(排序)-生产计划与控制（53页珍藏版）》请在金锄头文库上搜索。

1、第五节 排序问题 一、排序问题的基本概念 二、优先调度法则 三、单设备排序问题 四、流水作业排列排序问题 1、流水作业排序问题 2、最长流程时间Fmax的计算 3、约翰逊算法 4、一般n/m/p/ Fmax 问题的启发式算法 五、单件作业排序问题 六、服务部门的人员排序 第五节 排序问题 一、排序问题的基本概念 1、名词术语 2、假设条件 3、符号说明 4、排序问题的分类和表示方法 5、排序问题的评价标准（目标函数） 1、名词术语 （1）排序（Sequencing） ：确定工件在机器上的加工顺序。 （2）编制作业计划（Scheduling） 确定工件的加工顺序，并确定机器加 工每个工件的开始时

2、间和完成时间 （3）调度（控制）（Controlling） 对生产过程实施控制所采取的行动 派工（Dispatching）按作业计划的要求，将具体生产任务安 排到具体的机床上加工 赶工（Expediting）在实际进度落后于计划进度时采取的行动 排序的各个名词来自加工制造业，（机器、工件、工序、加工 时间），但此时它们的含义已经扩大了。如机器可以是人、计算机等 服务者。 （4）机器服务者 例如：工厂里的各种机床，维修工人，轮船要停靠的码头， （5）工件服务对象 例如：单个零件，或一批相同零件 （6）工序服务步骤 （7）加工时间服务时间 （8）加工顺序每台机器加工n 个工件的先后顺序 （9）加工

3、路线工件加工在技术上的工序顺序约束 由工艺过程决定 一般用M1，M2，Mm表示加工路线 例：某工件要经过车、铣、钻、磨的路线加工，可表示为： M1，M2，M3，M4 1、名词术语（续） 2、假设条件 （1）一个工件不能同时在几台不同的机器上加工。 （2）每道工序只在一台机器上。 （3）不允许中断：当一个工件一旦开始加工，必须一直进行到完工， 不得中途停止插入其它工件。 （4）每台设备只能胜任一道工序。 （5）工件数、机器数和加工时间已知，加工时间与加工顺序无关。 （6）每台机器同时只能加工一个零件（不考虑多工位组合机床）。 （7）工件在加工过程中采取平行移动方式 3、符号说明 Ji：工件i i

4、=1，2，n Mj：机器j j=1，2，m Pij： Ji在Mj上的加工时间 ri：Ji的到达时间（到达车间） Ci： Ji的完工时间Ci= ri+(ij+ Pij)= ri+ Wi+Pi Wi：Ji在加工过程中总的等待时间 Cmax：最大完工时间：当多个工件共同进入某个车间需要加工 时，每个零件都有一个完工时间，在这些完工时间中，最后 一个工件的完工时间称为最大完工时间。 di：Ji的完工期限 Fi： Ji的流程时间Fi= Ci-ri Fmax：最长流程时间 Li：工件的延迟时间 Li= Ci- di Li0 正延迟 实际完工完工期限 Libi的工件按bi值不增顺序排成序列B (3) 将A放

5、到B之前，构成最优加工顺序 J1J2J3J4J5J6 ai518534 bi722474 J2J5J6J4 45 44 3 7 1 2 J1J3 ai58 bi72 序列A为（J2，J5，J6，J1），序列B为（J4，J3），构成最优顺 序为（J2，J5，J6，J1，J4，J3） Johnson法则讨论 从应用Johnson法则求得的最优顺序中任意去掉一些工件时，余下 的工件仍构成最优顺序 例：最优顺序（2，5，6，1，4，3） 若去掉一些工件，得到的顺序（5，6，1，4，3），（2， 6，4，3），（2，6，1，4）仍为余下工件最优顺序 Johnson法则是充分条件，不是必要条件 不符合这个

6、法则的加工顺序，也可能是最优顺序 例：顺序（2，5，6，4，1，3）不符合Johnson法则，也是最 优顺序 CDS法（由Campbell，Dudek，Smith 提出） 把Johnson 算法用于一般的n/m/p/ Fmax 问题得到（m1）个加工顺 序，取其中最优者 具体做法是： 对每个工件计算 = = l k ik p 1 +=+= m lmk ik p 1 用约翰逊算法求（m-1）次加工顺序，取其中最好的结果。 和，l=1，2，m-1， (一) CDS法 4、一般n/m/p/ Fmax问题的启发式算法 用加工矩阵计算 Fmax 63 J1J2J3J4J5J6 56 10 12 2 5

7、3 9 pi131294 pi27468 pi34871 pi457115 解：右边例题中共有4个工序，该问题可 得到（m1）个加工顺序，即可得 到3个加工顺序，取其中最优者 步骤步骤1：l=1，取上表工序矩阵中首末两道工序按约翰逊算法排序，并计算最大流程时间，取上表工序矩阵中首末两道工序按约翰逊算法排序，并计算最大流程时间 J1J2J3J4J5J6 56 29 pi131294 pi457115 （ J1， J4， J5， J3， J2，J6） 用加工矩阵计算 Fmax 68 步骤步骤2： l=2，取前两道工序之和与末两道工序值和，形成一个两工序的矩阵，按约 翰逊算法排序，并计算最大流程时间

8、 ，取前两道工序之和与末两道工序值和，形成一个两工序的矩阵，按约 翰逊算法排序，并计算最大流程时间 J1J2J3J4J5J6 1016 1412 pi1 + pi210161512 pi3 + pi4915186 （ J5， J3， J2，J6， J1， J4） (一) CDS法（例题） = = l k ik p 1 +=+= m lmk ik p 1 J1J2J3J4J5J6 56 10 12 2 5 3 9 M131294 M27468 M34871 M457115 用加工矩阵计算 Fmax 67 步骤步骤3：l=3，取前三道工序之和与末三 道工序值和，形成一个两工序的 矩阵，按约翰逊算法

9、排序，并计 算最大流程时间 取前三道工序之和与末三 道工序值和，形成一个两工序的 矩阵，按约翰逊算法排序，并计 算最大流程时间 J1J2J3J4J5J6 1328 2417 pi1 + pi2 + pi3 14242213 pi2 + pi3 + pi416192414 （ J4， J5 ， J1， J3 ，J6， J2） 步骤步骤4：比较前面三步所得三种排序方案的三个：比较前面三步所得三种排序方案的三个Fmax，取其中最小者对应的排序方 案作为最终的排序方案。 ，取其中最小者对应的排序方 案作为最终的排序方案。 由以上步骤可知，当工序数目为由以上步骤可知，当工序数目为m时，需要用约翰逊算法进

10、行时，需要用约翰逊算法进行m-1次排序，形成次排序，形成m-1 个方案，计算个方案，计算m-1个个Fmax，找出其中最小的，找出其中最小的Fmax那个排序方案，就得到了所求的排序 方案。 那个排序方案，就得到了所求的排序 方案。 (一) CDS法（例题） = = l k ik p 1 +=+= m lmk ik p 1 （二） Palmer 法：按斜度指标排列工件的启发式算法 工件斜度指标： m为机器数；pik为工件 i在 Mk 上的加工时间，i=1，2，n。 按照各工件i不增的顺序排列工件，可得出令人满意的顺序。 ik m k i pmk = = +=+= 1 2/ )1( (二) Palm

11、er 法 (二) Palmer 法（例题） 1234 pi11263 Pi28429 Pi34582 例12-3 4/3/F/Fmax问题，其加工时间如表125所示，用Palmer法求解。 ik m k i pmk = = +=+= 1 2/ )1( 11 2/ )13(1p+= = k k pk 1 3 1 1 2/ )13( = = +=+= 1311 pp+ + = = 12 2/ )13(2p+ + + + 13 2/ )13(3p+ + + + 3 1 = = 3 2 = = 2 3 = = 1 4 = = 加工顺序为加工顺序为（1，2，3，4）或（2，1，3，4） Fmax28 3

12、41=+= 陈荣秋1983年提出的启发式算法 其步骤为： 计算每个工件的总加工时间Pi= pij，找出加工时间最长的工件C， 将其作为关键工件。 对余下工件，若pi1 pim，则按pi1不减的顺序排成一个序列Sa； 若pi1 pim则按pim不增的顺序排成一个序列Sb. 顺序（Sa，C，Sb）即为所求顺序。 （三） 关键工件法 1234 pi11263 pi28429 pi34582 pi 用关键工件法求解 13111614 总加工时间最长的为3号工件 pi1pim的工件为1和2，按pi1不减的顺序排成Sa（1，2） pi1 pim的工件为4号工件，Sb（4） 加工顺序为（1，2，3，4） （

13、三）关键工件法（例题） 第五节 排序问题 五、单件作业排序问题 1、问题的描述 2、 n/2/G/Fmax排序问题 3、n/m/G/Fmax排序问题 对于一般单件作业排序问题，每个工件都有其独特的加工路 线，工件没有一定的流向。要描述一道工序要三个参数：i，j，k ， i表示工件号，j表示工序号，k表示完成工件i的第j道工序的机器的 代号。因此，可以用（i，j，k）来表示工件i的第j道工序是在机器k 上进行的这样一件事。 加工描述矩阵和加工时间矩阵为： 它的第一行描述工件1的加工 ，第二行描述工件2的加工。它表 明，工件1的第一道工序在M1上进行，第二道工序在M3 上进行 = = 2,3,2

14、2,2,1 2,1,3 1,3,2 1,2,3 1,1,1 D 1、问题的描述 = = 3,4,5 2,4,1 T （1）将n个工件分为四类 第一类：只有一道工序，且这道工序是在M1上加工的工件属于A集合 第二类：只有一道工序，且这道工序是在M2上加工的工件属于B集合 第三类：有两道工序，且第一道工序在M1上加工，第二道工序在M2上加 工的工件属于AB集合 第四类：有两道工序，且第一道工序在M2上加工，第二道工序在M1上加 工的工件属于BA集合 （2）对于AB集合中的工件，按约翰逊算法排序，得到顺序SAB，对于BA 集合中的工件，按约翰逊算法排序，得到顺序SBA，对于A集合和 B集合中的工件，

15、可以按任意顺序排列，分别得到顺序SA和SB （3）在机器M1上工件按（SAB， SA，SBA）的顺序加工，在机器M2上工件 按（ SBA， SB， SAB）的顺序加工 2、n/2/G/Fmax排序问题 J1J2J3J4J5J6J7J8J9J10 设备设备M1M2M1M1M2M2M1M1M2M2 工时工时591274810957 设备设备M2M1M2M2M1M2M1 工时工时81271071110 第二 工序 第一 工序 第二 工序 第一 工序 AB集合中的工件集合中的工件J1，J3，J4，J8 BA集合中的工件集合中的工件J2，J6，J9 A集合中的工件集合中的工件J7 B集合中的工件集合中的工件J5，J10 排序后排序后 AB集合中的工件集合中的工件J1，J4，J8，J3 BA集合中的工件集合中的工件J9， J2，J6 B集合中的工件集合中的工件J10， J5 在在M1设备上的投产顺序设备上的投产顺序J1，J4，J8，J3，J7 ，J9， J2，J6 在在M2设备上的投产顺序设备上的投产顺序J9，J2， J6，J10， J5，