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

第五节排序问题 一、排序问题的基本概念 二、优先调度法则 三、单设备排序问题 四、流水作业排列排序问题 1、流水作业排序问题 2 、最长流程时间Fmax 的计算 3 、约翰逊算法 4 、一般n/m/p/ Fmax 问题的启发式算法 五、单件作业排序问题 六、服务部门的人员排序 第五节排序问题 一、排序问题的基本概念 1、名词术语 2 、假设条件 3 、符号说明 4 、排序问题的分类和表示方法 5 、排序问题的评价标准（目标函数） 1、名词术语 （1）排序（Sequencing）：确定工件在机器上的加工顺序。 （2 ）编制作业计划（Scheduling）确定工件的加工顺序，并确定机器加 工每个工件的开始时间和完成时间 （3）调度（控制）（Controlling）对生产过程实施控制所采取的行动 •派工（Dispatching ）——按作业计划的要求，将具体生产任务安 排到具体的机床上加工 •赶工（Expediting ）——在实际进度落后于计划进度时采取的行动 排序的各个名词来自加工制造业，（机器、工件、工序、加工 时间），但此时它们的含义已经扩大了。如机器可以是人、计算机等 服务者。 1、名词术语（续） （4 ）机器——服务者 例如：工厂里的各种机床，维修工人，轮船要停靠的码头，…… （5）工件——服务对象 例如：单个零件，或一批相同零件 （6）工序——服务步骤 （7）加工时间——服务时间 （8）加工顺序——每台机器加工n 个工件的先后顺序 （9）加工路线——工件加工在技术上的工序顺序约束 由工艺过程决定 一般用M1 ，M2 ，……，Mm 表示加工路线 例：某工件要经过车、铣、钻、磨的路线加工，可表示为： M ，M ，M ，M 1 2 3 4 2、假设条件 （1）一个工件不能同时在几台不同的机器上加工。 （2）每道工序只在一台机器上。 （3）不允许中断：当一个工件一旦开始加工，必须一直进行到完工， 不得中途停止插入其它工件。 （4）每台设备只能胜任一道工序。 （5）工件数、机器数和加工时间已知，加工时间与加工顺序无关。 （6）每台机器同时只能加工一个零件（不考虑多工位组合机床）。 （7）工件在加工过程中采取平行移动方式 3 、符号说明 J ：工件i i=1 ，2 ，┅，n i M ：机器j j=1 ，2 ，┅，m j P ：J 在M 上的加工时间 ij i j r ：J 的到达时间（到达车间） i i C ：J 的完工时间 C = r + Σ( ω+ P )= r + W +P i i i i ij ij i i i W ：J 在加工过程中总的等待时间 i i Cmax ：最大完工时间：当多个工件共同进入某个车间需要加工 时，每个零件都有一个完工时间，在这些完工时间中，最后 一个工件的完工时间称为最大完工时间。 3 、符号说明（续） d ：J 的完工期限 i i F ：J 的流程时间 F = C -r i i i i i Fmax ：最长流程时间 L ：工件的延迟时间 L = C - d i i i i L 0