第第1111章 制造业生产作业计划章 制造业生产作业计划
华中科技大学管理学院
陈荣秋
生产任务的最终落实生产任务的最终落实
nn MRP确定各车间的零部件投入出产计划，
将全厂性的产品出产计划变成了各车间
的生产任务。
nn 各车间要将车间的生产任务变成各个班
组、各个工作地和各个工人的任务，才
算落到实处。
nn 将任务安排到工作地，牵涉到任务分配
和作业排序问题
编制作业计划要解决的问题编制作业计划要解决的问题
nn 工厂里要对每个工人和工作地安排每天的生产工厂里要对每个工人和工作地安排每天的生产
任务，规定开始时间和完成时间；任务，规定开始时间和完成时间；
nn 医院要安排病人手术，为此要安排手术室、配医院要安排病人手术，为此要安排手术室、配
备手术器械、手术医师和护士；备手术器械、手术医师和护士；
nn 学校要安排上课时间表，使学生能按规定的时学校要安排上课时间表，使学生能按规定的时
间到规定的教室听事先安排的教师讲课。间到规定的教室听事先安排的教师讲课。
nn 项目计划管理，也是一个作业计划问题。项目计划管理，也是一个作业计划问题。
nn 英文英文SchedulingScheduling可以译成编制作业计划或安排可以译成编制作业计划或安排
日程计划日程计划((时间表时间表))。。
nn 编制作业计划实质上是要将资源分配给不同的编制作业计划实质上是要将资源分配给不同的
任务，按照既定的优化目标，确定各种资源利任务，按照既定的优化目标，确定各种资源利
用的时间问题。用的时间问题。
有关的名词术语有关的名词术语
nn 排序排序((Sequencing)Sequencing) 是确定零件在机器上的加是确定零件在机器上的加
工顺序。工顺序。
nn 编制作业计划编制作业计划((Scheduling)Scheduling)则不仅包括确定加则不仅包括确定加
工顺序，而且还包括加工任务的分配和加工每工顺序，而且还包括加工任务的分配和加工每
个零件的开始时间和完成时间。个零件的开始时间和完成时间。
nn ““调度调度””是作业计划编制后实施生产控制所采是作业计划编制后实施生产控制所采
取的一切行动，取的一切行动，““编制作业计划编制作业计划””是加工制造是加工制造
发生之前的活动。火车时刻表是作业计划。火发生之前的活动。火车时刻表是作业计划。火
车时刻表制定后，对火车运行的安排，包括发车时刻表制定后，对火车运行的安排，包括发
生晚点后的处理，都属于调度。生晚点后的处理，都属于调度。
名词术语名词术语((续续))
nn ““派派工工” (” (Dispatching)Dispatching)是在作业计划制定以是在作业计划制定以
后，按照作业计划的要求，将具体生产任务通后，按照作业计划的要求，将具体生产任务通
过工票或施工单的形式下达到具体的机床和工过工票或施工单的形式下达到具体的机床和工
人，属于通常所说的人，属于通常所说的““调度调度””范围。范围。
nn ““赶工赶工” (” (Expediting)Expediting)是在实际进度已落后是在实际进度已落后
于计划进度时采取的行动，也属于通常所说的于计划进度时采取的行动，也属于通常所说的
““调度调度””范围。范围。
nn ““机器机器””，可以是工厂里的各种机床，也可以，可以是工厂里的各种机床，也可以
是维修工人；可以是轮船要停靠的码头，也可是维修工人；可以是轮船要停靠的码头，也可
以是电子的计算机中央处理单元、存贮器和输以是电子的计算机中央处理单元、存贮器和输
入、输出单元。表示入、输出单元。表示““服务者服务者””；；
名词术语名词术语((续续))
nn “零件”则代表“服务对象”。零件可
以是单个零件，也可以是一批相同的零
件
nn “加工路线”是零件加工经过不同机器
构成的路线。比如，某零件要经过车、
铣、占、磨的路线加工，我们可以用
M
1
,M
2
,M
3
,M
4
来表示。
nn “加工顺序”则表示每台机器加工n个零
件的先后顺序，是排序要解决的问题
4 4参数表示法参数表示法::
nn n /m /A /Bn /m /A /B。。
其中其中, , n ──n ──零件数；零件数；
m ──m ──机器数；机器数；
A ──A ──作业类型；在作业类型；在AA的位置若标以的位置若标以
““F”F”，，则代表流水作业排序问题。若标以则代表流水作业排序问题。若标以
““P”P”，，则表示流水作业排列排序问题。若标则表示流水作业排列排序问题。若标
以以““G”G”，，则表示一般单件作业排序问题。当则表示一般单件作业排序问题。当mm
＝＝11，，则则AA处为空白处为空白
B──B──目标函数，通常是使其值最小。目标函数，通常是使其值最小。
流水作业计划问题流水作业计划问题
nn 流水线是流水车间(Flow shop) 典型的
代表，每个零件的加工路线都一致。
nn 只要加工路线一致：M1， M2, M3，…..
，Mm,不要求每个零件都经过每台机器加
工
最长流程时间最长流程时间FF
maxmax
的计算的计算
nn 最长流程时间又称作加工周期 最长流程时间又称作加工周期
6/4/6/4/p/p/ F F
maxmax
问题，当按顺序问题，当按顺序SS＝＝( (
6,1,5,2,4,3)6,1,5,2,4,3)加工时，求加工时，求FF
maxmax
..
nn 加工周期为46
n/2/F/n/2/F/FF
maxmax
问题的最优算法问题的最优算法
nn JohnsonJohnson算法：算法：
①① 从加工时间矩阵中找出最短的加工时 从加工时间矩阵中找出最短的加工时
间。间。
②② 若最短的加工时间出现在 若最短的加工时间出现在MM
11
上，则对上，则对
应的零件尽可能往前排；若最短加工时间出现应的零件尽可能往前排；若最短加工时间出现
在在MM
22
上，则对应零件尽可能往后排。然后，从上，则对应零件尽可能往后排。然后，从
加工时间矩阵中划去已排序零件的加工时间。加工时间矩阵中划去已排序零件的加工时间。
若最短加工时间有多个，则任挑一个若最短加工时间有多个，则任挑一个
③③ 若所有零件都已排序，停止。否则， 若所有零件都已排序，停止。否则，
转步骤转步骤①①。。
nn 求最优顺序
算法步骤的改进算法步骤的改进
nn 把Johnson算法作些改变，改变后的算法
按以下步骤进行：
nn ① 将所有ai≤bi的零件按ai值不减
的顺序排成一个序列A。
nn ② 将所有ai＞bi的零件按bi值不增
的顺序排成一个序列B。
nn ③ 将A放到B之前，就构成了最优
加工顺序
nn 序列序列AA为为 (2 (2，， 5 5，，66，，1)1)，序列，序列BB为为(4(4，，3)3)，构，构
成最优顺序为成最优顺序为 (2 (2，，55，，66，，11，， 4 4，，3)3)，与，与
JohnsonJohnson算法结果一致。算法结果一致。
nn Johnson法则只是一个充分条件，不是必
要条件。不符合这个法则的加工顺序，
也可能是最优顺序。如对例11-2顺序(2
，5，6，4，1，3)不符合Johnson法则，
但它也是一个最优顺序
nn 对于3台机器的流水车间排序问题，只有
几种特殊类型的问题找到了有效算法。
nn 对于一般的流水车间排列排序问题，可
以用分支定界法。
求一般求一般n/m/P/n/m/P/ F F
maxmax
问题近优解问题近优解
((Near optimal solution)Near optimal solution)的的
启发式算法启发式算法
nn 关键零件法
nn CDS法
nn 关键零件法求近优解举例
CDSCDS法法
nn Campbell-Dudek-Smith 三人提出了
一个启发式算法,简称CDS法。他们把
Johnson算法用于一般的n/m/P/F
max
问题，
得到(ｍ－1)个加工顺序，取其中优者
nn 当ｌ＝当ｌ＝11时，按时，按JohnsonJohnson算法得到加工顺序算法得到加工顺序(1(1，，
22，，33，，4)4)；； 当ｌ＝当ｌ＝22时，得到加工顺序时，得到加工顺序(2(2，，33
，，11，，4)4)。对于顺序。对于顺序(2(2，，33，，11，， 4) 4)，相应的，相应的
FF
maxmax
＝＝2929。。所以，取顺序所以，取顺序(1(1，，22，，33，，4)4)。我们已。我们已
经知道，这就是最优顺序。经知道，这就是最优顺序。
单件单件作业排序问题作业排序问题
nn 加工描述矩阵和加工时间矩阵
无延迟作业计划无延迟作业计划((non-delay non-delay
schedule)schedule)的构成的构成
nn 我们称每安排一道工序称作一“步”，
设
uu {{SS
tt
}──t}──t步步之之前前已已排排序序工工序序构构成成的的部部
分作业计划；分作业计划；
uu { { OO
tt
}──}──第第tt步步可可以以排排序序的的工工序序的的集集
合；合；
uu TT
kk
──{──{ OO
tt
}}中中工工序序OO
kk
的的最最早早可可能能开开工工
时间；时间；
uu TT
kk
’’ ──{──{ OO
tt
}}中中工工序序OO
kk
的的最最早早可可
能完工时间。能完工时间。
无延迟作业计划的构成步骤无延迟作业计划的构成步骤::
nn ①① 设 设tt＝＝11，，{S{S
11
}}为空集，为空集，{{OO
11
}}为各工件为各工件
第一道工序的集合。第一道工序的集合。
②② 求 求TT**＝＝min{min{TT
kk
}}，，并求出并求出TT**出现的机器出现的机器
MM**。。如果如果MM**有多台，则任选一台。有多台，则任选一台。
③③ 从 从{{OO
tt
}}中挑出满足以下两个条件的工中挑出满足以下两个条件的工
序序OO
jj
：：需要机器需要机器MM**加工，且加工，且TT
jj
＝＝TT**。。
④④ 将确定的工序将确定的工序OO
jj
放入放入{{SS
tt
}}，，从从{ { OO
tt
} }
中消去中消去OO
jj
，，并将并将OO
jj
的紧后工序放入的紧后工序放入{ { OO
tt
} }，，使使tt
＝＝tt＋＋11。。
⑤⑤ 若还有未安排的工序，转步骤若还有未安排的工序，转步骤②②；否；否
则，停止。则，停止。
优先派工法则优先派工法则
nn 在在介介绍绍无无延延迟迟作作业业计计划划的的构构成成步步骤骤时时，，其其中中第第
③③步步的的两两个个条条件件一一般般都都有有多多个个工工序序可可以以满满足足。。
按按什什么么样样的的准准则则来来选选择择可可安安排排的的工工序序，，对对作作业业
计计划划的的优优劣劣有有很很大大影影响响。。为为了了得得到到所所希希望望的的作作
业业计计划划，，人人们们提提出出了了很很多多优优先先调调度度法法则则，，按按优优
先先调调度度法法则则挑挑选选工工序序比比随随意意挑挑选选一一道道工工序序的的方方
法法更更能能符符合合计计划划编编制制者者的的要要求求，，同同时时又又不不必必列列
出所有可能的作业计划，从而计算量小。出所有可能的作业计划，从而计算量小。
nn 迄迄今今，，人人们们已已提提出出了了100100多多个个优优先先调调度度法法则则，，
其中主要的有下其中主要的有下88个：个：
nn ①① SPT(Shortest SPT(Shortest Processing Processing Time)Time)法法
则 优先选择加工时间最短的工序。则 优先选择加工时间最短的工序。
nn ②② FCFS(First FCFS(First Come Come First First Served)Served)法法
则 优先选择最早进入可排工序集合的工件。则 优先选择最早进入可排工序集合的工件。
优先派工法则优先派工法则((续续))
nn ③③ EDD(Earliest EDD(Earliest Due Due Date)Date)法法则则 优优先先
选择完工期限紧的工件。选择完工期限紧的工件。
nn ④④ MWKR(Most MWKR(Most Work Work Remaining)Remaining)法法则则
优先选择余下加工时间最长的工件。优先选择余下加工时间最长的工件。
nn ⑤⑤ LWKR(Least LWKR(Least Work Work Remaining)Remaining)法法则则
优先选择余下加工时间最短的工件。优先选择余下加工时间最短的工件。
nn ⑥⑥ MOPNR(Most MOPNR(Most Operations Operations Remaining)Remaining)
法则 优先选择余下工序数最多的工件。法则 优先选择余下工序数最多的工件。
nn ⑦⑦ SCR(Smallest SCR(Smallest Critical Critical Ratio)Ratio)法法则则
优优先先选选择择临临界界比比最最小小的的工工件件。。临临界界比比为为工工件件允允
许停留时间与工件余下加工时间之比。许停留时间与工件余下加工时间之比。
nn ⑧⑧ RANDOMRANDOM法则 随机地挑一个工件法则 随机地挑一个工件
随机抽样法随机抽样法
nn 用用穷穷举举法法或或分分支支定定界界法法求求一一般般单单件件车车间间排排序序问问
题题的的最最优优解解时时，，实实际际上上比比较较了了全全部部能能动动作作业业计计
划划；；采采用用优优先先调调度度法法则则求求近近优优解解时时，，只只选选择择了了
一种作业计划。一种作业计划。
nn 随机抽样法介于这两个极端之间。 随机抽样法介于这两个极端之间。
nn 它从全部无延迟作业计划之中抽样，得出多个它从全部无延迟作业计划之中抽样，得出多个
作业计划，从中选优。作业计划，从中选优。
nn 应用随机抽样法时，实际上是对同一个问题多应用随机抽样法时，实际上是对同一个问题多
次运用次运用RANDOMRANDOM法则来决定要挑选的工序，从而法则来决定要挑选的工序，从而
得到多个作业计划。得到多个作业计划。
概率调度法概率调度法
nn 随机抽样法是从随机抽样法是从kk个可供选择的工序以等概率个可供选择的工序以等概率
方式挑选，每个工序被挑选的概率为方式挑选，每个工序被挑选的概率为11／／kk，，这这
种方法没有考虑不同工序的特点，有一定盲目种方法没有考虑不同工序的特点，有一定盲目
性。性。
nn 例如，在构在无延迟作业计划的第例如，在构在无延迟作业计划的第③③步有步有33道道
工序，工序，AA、、BB和和CC可挑选，这可挑选，这33道工序所需的时间道工序所需的时间
分别为分别为33，，44和和77。如果按。如果按RANDOMRANDOM法则，每道工法则，每道工
序挑选上的概率都是序挑选上的概率都是11／／33；如果按；如果按SPTSPT法则，法则，
则只能挑选工序则只能挑选工序AA。现按目标函数的要求，选。现按目标函数的要求，选
择了择了SPTSPT法则。按概率调度法，将这法则。按概率调度法，将这33道工序按道工序按
加工时间从小到大排列，然后给每道工序从大加工时间从小到大排列，然后给每道工序从大
到小分配一个被挑选的概率，比如到小分配一个被挑选的概率，比如AA、、BB和和CC的的
挑选概率分别为挑选概率分别为66／／1414、、55／／1414和和33／／1414。。
