生产作业计划与排序.pptx

第六章生产作业计划与排序一、基本概念排序的作用方案1：白-灰-红-蓝T-setup=12方案2：蓝-红-灰-白T-setup=20按最短工时优先原则（SPT）,结果最优。一、基本概念一、基本概念一、基本概念一、基本概念排序问题的分类一、基本概念一、基本概念一、基本概念一、基本概念符号说明wij-----工件i在第j道工序的等待时间
Wi------工件i总的等待时间
Wi=wij
Ci------工件i的完工时间
Ci=ri+Wi+Pi
Fi------工件i的流程时间
Fi=Ci－ri=Wi+Pi
Li------工件i的延迟时间
Li=Ci－di
一、基本概念二、最长流程时间二、最长流程时间二、最长流程时间二、最长流程时间三、n/2/F/Fmax问题的算法三、n/2/F/Fmax问题的算法n/2/F/Fmax流水型排序四、一般n/m/P/Fmax问题的启发式算法四、一般n/m/P/Fmax问题的启发式算法四、一般n/m/P/Fmax问题的启发式算法四、一般n/m/P/Fmax问题的启发式算法四、一般n/m/P/Fmax问题的启发式算法四、一般n/m/P/Fmax问题的启发式算法问题描述
流水(i,j)(工件，工序)
单件(i,j,k)(工件，工序，机器)

加工描述矩阵和加工时间矩阵
五、单件车间排序问题（n/m/G/Fmax）五、单件车间排序问题（n/m/G/Fmax）五、单件车间排序问题（n/m/G/Fmax）五、单件车间排序问题（n/m/G/Fmax）五、单件车间排序问题（n/m/G/Fmax）五、单件车间排序问题（n/m/G/Fmax）一个实例：得到加工顺序矩阵：五、单件车间排序问题（n/m/G/Fmax）五、单件车间排序问题（n/m/G/Fmax）一个实例：得到加工顺序矩阵：4、启发式算法：
能动作业计划和无延迟作业计划尽管不一定是最优作业计划，但一般是较好的作业计划，特别是无延迟作业计划能提供令人满意的解。
一般能动作业计划和无延迟作业计划都有多个，可用启发式方法从中选择结果较好的作业计划。
一般来说，以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好。优选调度法则：
SPT(ShortestProcessingTime)法则：优先选择加工时间最短的工序。
FCFS(FirstComeFirstServed)法则：优先选择最早进入可排工序集合的工件。
EDD(EarliestDueDate)法则：优先选择完工期限紧的工件。
MWKR(MostWorkRemaining)法则：优先选择余下加工时间最长的工件。
LWKR(LeastWorkRemaining)法则：优先选择余下加工时间最短的工件。
MOPNR(MostOperationsRemaining)法则：优先选择余下工序数最多的工件。
SCR(SmallestCriticalRatio)法则：优先选择临界比最小的工件。演讲完毕，谢谢观看！