制造业生产作业计划
第11章　
华中科技大学管理学院

生产任务的最终落实
MRP确定各车间的零部件投入出产计划，将全厂性的产品出产计划变成了各车间的生产任务。
各车间要将车间的生产任务变成各个班组、各个工作地和各个工人的任务，才算落到实处。
将任务安排到工作地，牵涉到任务分配和作业排序问题
编制作业计划要解决的问题
工厂里要对每个工人和工作地安排每天的生产任务，规定开始时间和完成时间；
医院要安排病人手术，为此要安排手术室、配备手术器械、手术医师和护士；
学校要安排上课时间表，使学生能按规定的时间到规定的教室听事先安排的教师讲课。
项目计划管理，也是一个作业计划问题。
英文Scheduling可以译成编制作业计划或安排日程计划(时间表)。
编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。
有关的名词术语
排序(Sequencing) 是确定零件在机器上的加工顺序。
编制作业计划(Scheduling)则不仅包括确定加工顺序，而且还包括加工任务的分配和加工每个零件的开始时间和完成时间。
“调度”是作业计划编制后实施生产控制所采取的一切行动，“编制作业计划”是加工制造发生之前的活动。火车时刻表是作业计划。火车时刻表制定后，对火车运行的安排，包括发生晚点后的处理，都属于调度。
名词术语(续)
“派工” (Dispatching)是在作业计划制定以后，按照作业计划的要求，将具体生产任务通过工票或施工单的形式下达到具体的机床和工人，属于通常所说的“调度”范围。
“赶工” (Expediting)是在实际进度已落后于计划进度时采取的行动，也属于通常所说的“调度”范围。
“机器”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元。表示“服务者”；
名词术语(续)
“零件”则代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件
“加工路线”是零件加工经过不同机器构成的路线。比如，某零件要经过车、铣、占、磨的路线加工，我们可以用M1,M2,M3,M4来表示。
“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序要解决的问题
4参数表示法:
　　　　n /m /A /B。 其中, n ──零件数； m ──机器数； A ──作业类型；在A的位置若标以“F”，则代表流水作业排序问题。若标以“P”，则表示流水作业排列排序问题。若标以“G”，则表示一般单件作业排序问题。当m＝1，则A处为空白 B──目标函数，通常是使其值最小。
流水作业计划问题
流水线是流水车间(Flow shop) 典型的代表，每个零件的加工路线都一致。
只要加工路线一致：M1， M2, M3，…..，Mm,不要求每个零件都经过每台机器加工
最长流程时间Fmax的计算
　　最长流程时间又称作加工周期 　　6/4/p/ Fmax问题，当按顺序S＝( 6,1,5,2,4,3)加工时，求Fmax.

加工周期为46
n/2/F/Fmax问题的最优算法
　Johnson算法： 　　①　从加工时间矩阵中找出最短的加工时间。 　　②　若最短的加工时间出现在M1上，则对应的零件尽可能往前排；若最短加工时间出现在M2上，则对应零件尽可能往后排。然后，从加工时间矩阵中划去已排序零件的加工时间。若最短加工时间有多个，则任挑一个 　　③　若所有零件都已排序，停止。否则，转步骤①。

求最优顺序
算法步骤的改进
把Johnson算法作些改变，改变后的算法按以下步骤进行：
　　①　将所有ai≤bi的零件按ai值不减的顺序排成一个序列A。
　　②　将所有ai＞bi的零件按bi值不增的顺序排成一个序列B。
　　③　将A放到B之前，就构成了最优加工顺序

序列A为 (2， 5，6，1)，序列B为(4，3)，构成最优顺序为 (2，5，6，1， 4，3)，与Johnson算法结果一致。

Johnson法则只是一个充分条件，不是必要条件。不符合这个法则的加工顺序，也可能是最优顺序。如对例11-2顺序(2，5，6，4，1，3)不符合Johnson法则，但它也是一个最优顺序 
对于3台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法。
对于一般的流水车间排列排序问题，可以用分支定界法。
求一般n/m/P/ Fmax问题近优解 (Near optimal solution)的启发式算法 　　
关键零件法
CDS法　　

关键零件法求近优解举例
CDS法
Campbell-Dudek-Smith 三人提出了一个启发式算法,简称CDS法。他们把Johnson算法用于一般的n/m/P/Fmax问题，得到(ｍ－1)个加工顺序，取其中优者

当ｌ＝1时，按Johnson算法得到加工顺序(1，2，3，4)； 当ｌ＝2时，得到加工顺序(2，3，1，4)。对于顺序(2，3，1， 4)，相应的Fmax＝29。所以，取顺序(1，2，3，4)。我们已经知道，这就是最优顺序。
单件作业排序问题
加工描述矩阵和加工时间矩阵
无延迟作业计划(non-delay schedule)的构成

我们称每安排一道工序称作一“步”，设
　　{St}──t步之前已排序工序构成的部分作业计划；
　　{ Ot }──第t步可以排序的工序的集合；
　　Tk　──{ Ot }中工序Ok的最早可能开工时间；
Tk’　──{ Ot }中工序Ok的最早可能完工时间。 

无延迟作业计划的构成步骤:
　①　设t＝1，{S1}为空集，{O1}为各工件第一道工序的集合。 　　②　求T*＝min{Tk}，并求出T*出现的机器M*。如果M*有多台，则任选一台。 　　③　从{Ot}中挑出满足以下两个条件的工序Oj：需要机器M*加工，且Tj＝T*。 　　④　将确定的工序Oj放入{St}，从{ Ot }中消去Oj，并将Oj的紧后工序放入{ Ot }，使t＝t＋1。 　　⑤　若还有未安排的工序，转步骤②；否则，停止。

优先派工法则
在介绍无延迟作业计划的构成步骤时，其中第③步的两个条件一般都有多个工序可以满足。按什么样的准则来选择可安排的工序，对作业计划的优劣有很大影响。为了得到所希望的作业计划，人们提出了很多优先调度法则，按优先调度法则挑选工序比随意挑选一道工序的方法更能符合计划编制者的要求，同时又不必列出所有可能的作业计划，从而计算量小。
迄今，人们已提出了100多个优先调度法则，其中主要的有下8个：
　　①　SPT(Shortest Processing Time)法则　优先选择加工时间最短的工序。
　　②　FCFS(First Come First Served)法则　优先选择最早进入可排工序集合的工件。
优先派工法则(续)
　　③　EDD(Earliest Due Date)法则　优先选择完工期限紧的工件。
　　④　MWKR(Most Work Remaining)法则　优先选择余下加工时间最长的工件。
　　⑤　LWKR(Least Work Remaining)法则　优先选择余下加工时间最短的工件。
　　⑥　MOPNR(Most Operations Remaining)法则　优先选择余下工序数最多的工件。
　　⑦　SCR(Smallest Critical Ratio)法则　优先选择临界比最小的工件。临界比为工件允许停留时间与工件余下加工时间之比。
　　⑧　RANDOM法则　随机地挑一个工件
随机抽样法
用穷举法或分支定界法求一般单件车间排序问题的最优解时，实际上比较了全部能动作业计划；采用优先调度法则求近优解时，只选择了一种作业计划。
　　随机抽样法介于这两个极端之间。
它从全部无延迟作业计划之中抽样，得出多个作业计划，从中选优。
应用随机抽样法时，实际上是对同一个问题多次运用RANDOM法则来决定要挑选的工序，从而得到多个作业计划。
概率调度法
随机抽样法是从k个可供选择的工序以等概率方式挑选，每个工序被挑选的概率为1／k，这种方法没有考虑不同工序的特点，有一定盲目性。
例如，在构在无延迟作业计划的第③步有3道工序，A、B和C可挑选，这3道工序所需的时间分别为3，4和7。如果按RANDOM法则，每道工序挑选上的概率都是1／3；如果按SPT法则，则只能挑选工序A。现按目标函数的要求，选择了SPT法则。按概率调度法，将这3道工序按加工时间从小到大排列，然后给每道工序从大到小分配一个被挑选的概率，比如A、B和C的挑选概率分别为6／14、5／14和3／14。

制造业生产作业计划