第6章--作业排序.pptVIP

第 六 章作 业 排 序 第一节 概述 1、问题分类 第一节 概述 2、几个概念 第一节 概述 （2）延期与误期时间、时差 延期时间Li：实际完工时间Ci减去应交货时间Di。 Li＝ Ci－ Di 误期时间Ti：若Li0,则Ti＝Li ；否则，Ti＝0。 时差Sli：Sli＝Di－ti－ri。 ti是加工时间。 第一节 概述 （3）排序的目标 使平均流程时间极小化， 使总流程时间极小化， 使最长延期时间极小化， 使平均延期时间极小化， 使平均误期时间极小化， 使误期零件个数极小化，等 第二节 排序理论 第二节 排序理论 1、单台机床排序问题 考虑多个零件在一台机床上的排序问题 （1）SPT规则（使平均流程时间最短） 按加工时间由小到大的顺序排序。例如 第二节 排序理论 1、单台机床排序问题 （2）EDD规则（使最长延期时间最短） 按交货期由小到大的顺序排序。例如 第二节 排序理论 1、单台机床排序问题 例： 例： 第二节 排序理论 1、单台机床排序问题 （4）最短时差（Slack）规则 作用：缩短平均误期时间，但不能必然求出最优解。 方法：求出每项工作的时差，找出时差小者优先安排。 第二节 排序理论 1、单台机床排序问题 已排序序列 第二节 排序理论 1、单台机床排序问题 Step1：对所有任务按EDD规则排序。将EDD序的前两项任务记作a、b，比较a、b，若max{ ta, tb } ≤ max{ da, db},将a放在A栏，b放在B栏；否则，将最短的任务放在A栏，另一项放在B栏。EDD序中的第三项任务放在C栏。 Step2：比较B和C栏看B栏的任务能否进入已排序序列。若tB ≤tC，或FA＋max{ tB, tC}≤ max{ dB, dC}，将B栏的任务移到A栏，C栏的任务移到B栏，EDD序中的下一项任务变为C栏。如果EDD序中不再有任务，将A和B栏的任务移到已排序序列，并停止。否则，重复Step2。如果上述两个条件均不满足，转Step3. Step3：将B栏任务放回EDD序列，并将C栏移到B栏。比较A、B看B是否能进入A的已排序序列。如果tA ≤tB或如果FA－tA＋max{ tA, tB }≤ max {dA, dB}，将B栏任务移到A栏，从EDD序列中选择下两项任务作为新的B、C栏任务。回到Step2。如果两个条件均不满足，转Step4。 Step4：将A栏的任务放回到EDD序列中，并指定进入已排序序列中的最后一项任务作为新的A，返回到Step3。如果已排序序列没有任务存在，将B放到已排序序列，并使EDD序列的前两项任务分别变为B、C，转Step2。 第二节 排序理论 3、多台机床的同工艺顺序排序问题 一个例子。 (3) 关键零件法 第二节 排序理论 3、多台机床的同工艺顺序排序问题 (4) 最小排序系数法 对每个零件，计算一个排序系数；再按排序系数由小到大的顺序对所有零件排序。第j个零件的排序系数Kj按下式计算： 将两台机床记为A、B。借助于Johnson算法处理。 （1）将所有零件分为四类 {AB}：先在A，后在B上加工的零件； {BA}：先在B，后在A上加工的零件； {A}：仅在A上加工的零件； {B}：仅在B上加工的零件。 （2）分别对{AB}、 {BA}中的零件用Johnson规则排序，结果分别记作序（ AB ）、序（ BA ）。对{A}、 {B}中的零件均按任意顺序排序，结果分别记作序（ A）、序（ B ）。 （3）各零件在A上的加工顺序：序（AB），序（A），序（BA）； 各零件在B上的加工顺序：序（BA），序（B），序（AB）。 看一个例子。 求解下列问题。 画图求解。先看一个例子（P238），工艺顺序：M1→ M4。 第二节 排序理论 6、多个零件在多台并行机床的排序问题 （1）问题描述：考虑有m台并行机床。 （2）算法1：缩短平均流程时间 Step1. 对所有工作按SPT规则排序； Step2.每次从排序的前端取一个工作，将其安排在已安排总时间最小的机床上。任意破结。