文档介绍：第11章制造业作业计划与控制Scheduling and Controlling for Manufacturing
作业计划问题的基本概念
流水作业排序问题
编制作业计划要解决的问题
编制作业计划实质上是要将资源分配给不同的任务,按照既定的优化目标,确定各种资源利用的时间问题。
由于每台机器都可能被分配了多项任务,而这些任务受到加工路线的约束,带来了零件在机器上加工的顺序问题。
(续)
有关的名词术语
编制作业计划(Scheduling)-排程
排序(Sequencing)
派工(Dispatching)
控制(Controlling)
赶工(Expediting)
“调度”是作业计划编制后实施生产控制所采取的一切行动,“编制作业计划”是加工制造发生之前的活动。
(续)
“机器”,可以是工厂里的各种机床,也可以是维修工人;可以是轮船要停靠的码头,也可以是电子的计算机中央处理单元、存贮器和输入、输出单元。一句话,表示“服务者”
“零件”代表“服务对象”。零件可以是单个零件,也可以是一批相同的零件
“加工路线”是零件加工的工艺过程决定的,它是零件加工在技术上的约束
“加工顺序”则表示每台机器加工n个零件的先后顺序,是排序和编制作业计划要解决的问题
1、假设条件与符号说明
6个假设条件、7个符号
2、排序问题表示法
Conway(康威)、4个参数
流水作业排序问题
流水车间(Flow shop):工件的加工路线都一致,典型的如流水线
最长流程时间的计算
两台机器排序问题的最优算法
多台机器排序问题的启发式算法
Work Center #1
Work Center #2
Output
最长流程时间的计算
工件代号i
1 4 6 3 5 2
Pi1 4 5 3 4 8 6
Pi2 3 9 1 3 7 5
Pi3 7 6 8 2 5 9
Pi4 5 6 3 9 2 4
4 9 12 16 24 30
7 18 19 22 31 36
14 24 32 34 39 48
19 30 35 44 46 52
两台机器排序问题的最优算法
约翰森法则
如果Min(ai, bj) < Min (aj, bi),则工件i应该排在工件j之前。
约翰森算法
(1)从加工时间矩阵中找出最短加工时间;
(2)若最短加工时间出现在机器M1 上,则对应工件应该尽可能往前排;若最短加工时间出现在机器M2 上,则对应工件应该尽可能往后排。
两台机器排序问题的最优算法(续)
然后从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个,则任挑一个。
(3)若所有工件都已排序,停止。否则,转步骤(1)。
将工件2排在第1位 2
将工件3排在第6位 2 3
将工件5排在第2位 2 5 3
将工件6排在第3位 2 5 6 3
将工件4排在第5位 2 5 6 4 3
将工件1排在第4位 2 5 6 1 4 3
最优加工顺序为S=(2,5,6,1,4,3), Fmax =28
I 1 2 3 4 5 6
Ai 5 1 8 5 3 4
Bi 7 2 2 4 7 4
两台机器排序问题的最优算法(续)