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

J3 8 2
1 2
8
26 J3
J4
M2 3
J5J4 22
J3 26 28
5
10
15
20
25
30 时间
2、最长流程时间Fmax 的计算
◆ 最长流程时间（加工周期） 从第一个工件在第一台机器开始加工时算起，到最后一个 工件在最后一台机器上完成加工时为止所经过的时间 ◆ 假设所有工件的到达时间都为零 ri= 0, i= 1, 2, ……n Fmax等于排在末位加工的工件在车间的停留时间，也等于 一批工件的最大完工时间Cmax ◆ 设n 个工件的加工顺序为 S= ( S1, S2,……Sn） Si为排第i 位加工的工件的代号
1、名词术语 2、假设条件 3、符号说明 4、排序问题的分类和表示方法 5、排序问题的评价标准（目标函数）
1、名词术语
（1）排序（Sequencing） ：确定工件在机器上的加工顺序。 （2）编制作业计划（Scheduling） 确定工件的加工顺序，并确定机器加 工每个工件的开始时间和完成时间 （3）调度（控制）（Controlling） 对生产过程实施控制所采取的行动 •派工（Dispatching）——按作业计划的要求，将具体生产任务安 排到具体的机床上加工 •赶工（Expediting）——在实际进度落后于计划进度时采取的行动 排序的各个名词来自加工制造业，（机器、工件、工序、加工 时间），但此时它们的含义已经扩大了。如机器可以是人、计算机等 服务者。
5、排序问题的评价标准（目标函数）
（1）以按时交货作为目标函数 平均延迟时间 L 平均延误时间 T 最大延误时间Tmax 延误的工件数n （2）以工件的完工时间和工件的流程时间为目标函数 最大完工时间Cmax 最长流程时间Fmax 平均完工时间 C 平均流程时间 F （3）其他目标函数 在制品占用量最小 总调整时间最小 延期罚款最小 生产费用最小 总利润最大 设备利用率最大
时，每个零件都有一个完工时间，在这些完工时间中，最后 一个工件的完工时间称为最大完工时间。
3、符号说明（续）
di：Ji的完工期限 Fi： Ji的流程时间 Fi= Ci-ri Fmax：最长流程时间 Li：工件的延迟时间 Li = Ci- di Li>0 正延迟 实际完工>完工期限 Li<0 负延迟 Li=0 零延迟 Ti：工件的延误时间 Lmax：最长延迟时间 Ti ＝ max {Li ，0}
三、单设备排序问题
单设备排序问题是最简单的排序问题，但在单件小批生产中，对于 关键设备具有重要意义，它往往能够缩短工件等待时间，减少在制品占 用量，提高设备利用率和生产面积利用率，满足用户的不同需求。
定理1：对于单设备排序问题，SPT规则使平均流程时间最短 定理2：对于单设备排序问题，EDD规则使最大延迟或最大延误时间最短。 例题1：5个工件的单机作业排序问题的资料如下，分别用SPT规则和EDD规 则进行排序。
M1，M2，M3，M4
2、假设条件
（1）一个工件不能同时在几台不同的机器上加工。 （2）每道工序只在一台机器上。 （3）不允许中断：当一个工件一旦开始加工，必须一直进行到完工， 不得中途停止插入其它工件。 （4）每台设备只能胜任一道工序。 （5）工件数、机器数和加工时间已知，加工时间与加工顺序无关。 （6）每台机器同时只能加工一个零件（不考虑多工位组合机床）。 （7）工件在加工过程中采取平行移动方式
四、流水作业排列排序问题
1、流水作业排序问题 2、最长流程时间Fmax 的计算 3、约翰逊算法 4、一般n/m/p/ Fmax 问题的启发式算法
1、流水作业排序问题
◆ 流水作业排序问题的基本特征：每个工件加工路线一致。 ※ 工件的流向一致 ※ 并不要求每个工件必须经过加工路线上每台机器加工。 ※ 不经过某台机器时，加工时间可以设为零。 ¾一般流水作业排序问题：工件在不同机器上的加工顺序不一定相同。 ¾流水作业排列排序问题：所有工件在各个不同机器上的加工顺序都相同。
二、优先调度规则
作业排序问题非常复杂，82％的问题属于NP难题，许多问题采用优先 调度法则或启发式算法来解决生产任务对设备需求的冲突。共有100多个， 其中有8个是主要的 ① SPT( Short processing time) ◆ 优先选择加工时间最短的任务， ◆ 平均流程时间最短 ② FCFS ( First come first served) ◆优先选择最早进入可排工序集合的工件 ◆来自排队论，对工件较公平 ③ EDD ( Earliest due date ) ◆优先选择完工日期最早的任务 ◆可使工件最大延误时间最小 ④ MWKR ( Most work remaining) ◆优先选择余下加工时间最长的工件 ◆不同工作量的工件的完工时间尽量接近
EDD
工件号 作业时间 交货期 开始时间 结束时间 延迟L 误期T
J4 5 6 1 5 -1 0
J3 1 8 6 6 -2 0
J5 4 14 7 10 -4 0
J2 7 20 11 17 -3 0
J1 3 23 18 20 -3 0
工件号 作业时间 交货期 开始时间 结束时间 延迟L 误期T
J3 1 8 1 1 -7 0
三、单设备排序问题
工件号 作业时间 交货期 SPT EDD J1 3 23 J2 7 20 J3 1 8 J4 5 6 J5 4 14
工件号 作业时间 交货期 开始时间 结束时间 延迟L 误期T
J3 1 8 1 1 -7 0
J1 3 23 2 4 -19 0
J5 4 14 5 8 -6 0
J4 5 6 9 13 7 7
C k ( si ) = max C ( k −1)(S i ) , C k (S i-1 ) + pS i k
k=2，3，…，m ◆ 当ri=0，i=1，2，…，n i=1，2，…，n
{
}
F max= C m (S n )
2、最长流程时间Fmax 的计算（例题）
例1：6/4/p/ Fmax ，其加工时间如表1所示。 J1 M1 M2 M3 M4 2 5 8 2 J2 1 7 5 3 J3 2 5 5 1 J4 4 4 5 3 J5 3 6 7 4 J6 4 4 5 4
1、名词术语（续）
（4）机器——服务者 例如：工厂里的各种机床，维修工人，轮船要停靠的码头，…… （5）工件——服务对象 例如：单个零件，或一批相同零件 （6）工序——服务步骤 （7）加工时间——服务时间 （8）加工顺序——每台机器加工n 个工件的先后顺序 （9）加工路线——工件加工在技术上的工序顺序约束 由工艺过程决定 一般用M1，M2，……，Mm 表示加工路线 例：某工件要经过车、铣、钻、磨的路线加工，可表示为：
第五节 排序问题
一、排序问题的基本概念 二、优先调度法则 三、单设备排序问题 四、流水作业排列排序问题 1、流水作业排序问题 2、最长流程时间Fmax 的计算 3、约翰逊算法 4、一般n/m/p/ Fmax 问题的启发式算法 五、单件作业排序问题 六、服务部门的人员排序
第五节 排序问题
一、排序问题的基本概念
J2 7 20 14 20 0 0
工件号 作业时间 交货期 开始时间 结束时间 延迟L 误期T
J4 5 6 1 5 -1 0
J3 1 8 6 6 -2 0
J5 4 14 7 10 -4 0
J2 7 20 11 17 -3 0
J1 3 23 18 20 -3 0
Fmax = 1 + 3 + 4 + 5 + 7 = 20
4、排序问题的分类和表示方法
（1）按机器的种类数量不同 ① ② 单台 多台 流水作业(Flow-shop)排序： 所有工件的加工路线完全相同 （2）按到达车间的情况不同 ① ② 静态排序问题：排序时所有工件已到达，对它们进行一次排序。 动态排序问题：工件陆续到达，随时安排它们的加工顺序。 单件作业（Job-shop）排序：工件的加工路线不同
3、符号说明
Ji：工件i Mj：机器j i=1，2，┅，n j=1，2，┅，m
Pij： Ji在Mj上的加工时间 ri：Ji的到达时间（到达车间） Ci： Ji的完工时间 Ci= ri+Σ(ωij+ Pij)= ri+ Wi+Pi
Wi：Ji在加工过程中总的等待时间 Cmax：最大完工时间：当多个工件共同进入某个车间需要加工
2、最长流程时间Fmax 的计算（续）
◆
C k ( si ) pS i k
：Si在机器Mk上的完工时间 ：Si在机器Mk上的加工时间 k=2，3，…，m
k从2开始说明最长流 程时间的计算对于在 两个设备上的排序问
i=1，2，…，n 题有意义。对于单个 设备无论如何排序都 是这么长。
◆
C1( si ) = C1 si −1 + pS i 1
※ 其最优解不一定是相应的流水作业排序问题的最优解，但一般是比较好的解 ※ 对于仅有2台和3台机器的特殊情况，排列排序问题最优解一定是相应流水作业排 序问题的最优解
2、最长流程时间Fmax 的计算
J2 ai bi
1 M1 J5 4 J6
J5 3 7
13 J1
J6 4 4
J1 5 7
18
J4 5 4
（3）按目标的不同 ① ② 平均流程时间最短 误期完工工件最少等
（4）按目标函数的性质 ① ② 单目标 多目标
4、排序问题的分类和表示方法（续）
（5）按参数的性质 ① ② 确定型：加工时间和其他参数是已知确定的量。 随机型：加工时间和其他参数是随机的量。 表示方法（Conway等人提出的）： n/m/A/B n为工件数。 m为机器数。当m=1时，A处为空白。 B为目标函数，通常是使其值最小。 F表示流水作业排序问题。 A为车间类型 P表示流水作业排列排序问题 G表示一般单件作业排序问题。 例：n／3／p／Cmax表示n个工件经3台机器加工的流水作业排 列排序问题，目标函数是使最长完工时间Cmax最短