算法大全：32第三十二章 作业计划

普大帝

你好！我是陪你一起进阶人生的普大帝！愿你成才！祝你成长！
为大家更新一些算法类的辅助资料，大家在想学习时，或者比赛急需时就可以按照对应的名字找到对应的算法，加以应用了。大家按照下图所示箭头处点击主题，就可以查看到其他算法类内容了，或者搜索框内输入算法大全，也可以搜索到对应的贴子，本篇为第32篇。

作业计划

排序的理论与方法是编制车间作业计划的基础。本章将介绍排序问题的基本概念，重点介绍流水作业排序问题。
§1 流水车间调度问题
1.1 排序问题的基本概念
1.1.1 名词术语在生产管理中，常用到“编制作业计划”（Scheduling）、“排序”（Sequencing）、“派工”（Dispatching） 、“控制”（Controlling）和“赶工”（Expediting）这些名词。一般说来，编制作业计划与排序不是同义语。排序只是确定工件在机器上的加工顺序。而编制作业计划，则不仅包括确定工件的加工顺序，而且还包括确定机器加工每个工件的开始时间和完成时间。因此，只有作业计划才能指导每个工人的生产活动。由于编制作业计划的主要问题是确定各台机器上工件的加工顺序，而且，在通常情况下都是按最早可能开(完)工时间来编排作计划的。因此，当工件的加工顺序确定之后，作业计划也就确定了。所以，人们常常不加区别地使用“排序”与“编制作业计划”这两个术语。在本章里，讲排序的时候就暗指相应的作业计划是最早时间作业计划。只有在需要的时候，才将这两个术语区别使用。“派工”是按作业计划的要求，将具体生产任务安排到具体的机床上加工，属于我们经常说的“调度”范围。“赶工”是在实际进度已落后于计划进度时采取的行动，也属于“调度”范围。“调度”是实行控制所采取的行动。“编制作业计划”是加工制造发生之前的活动；“调度”是在加工制造发生之后的活动。调度的依据是作业计划。比如，火车时刻表是一种作业计划，火车发生晚点，就要进行调度。调度是一种现场指挥。描述排序问题的名词术语来自加工制造行业。为了和惯用的名词术语保持一致，本书仍使用“机器”、“工件”、“工序”和“加工时间”等术语来描述各种不同的排序问题。但要注意，它们已不限于本来的含义。这里所说的“机器”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子计算机中央处理单元、存贮器和输入、输出单元。一句话，表示“服务者”；工件则代表“服务对象”。工件可以是单个零件，也可以是一批相同的零件。假定有 n 个工件要经过 m 台机器加工。“加工路线”是工件加工的工艺过程决定的，它是工件加工在技术上的约束。比如，某工件要经过车、铣、占、磨的路线加工，我们可以用M1 M2 M3 M4 来表示。L 来表示加工路线。“加工顺序”则表示每台机器加工 n 个工件的先后顺序，是排序要解决的问题。
1.1.2 假设条件与符号说明为了便于分析研究，建立数学模型，有必要对排序问题提出一些假设条件。
$ j4 b3 @0 ]7 y4 s$ b: |3 j9 X① 一个工件不能同时在几台不同的机器上加工。
7 M4 z& q2 [4 w. B: h② 工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。
③ 不允许中断。当一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其它工件。
④ 每道工序只在一台机器上完成。
( |3 M' A# G  o) M7 y; y# n" k⑤ 工件数、机器数和加工时间已知，加工时间与加工顺序无关。
⑥ 每台机器一次只能加工一个工件。
# P) u& f3 ~* v, K+ q
5 n1 F: b1 l6 _, l7 y3 g" p
1 M+ N1 z, n4 ~# G1.1.3 排序问题的分类和表示法
  S8 v) J5 j: N排序问题有不同的分类方法。最常用的分类方法是按机器、工件和目标函数的特征分类。按机器的种类和数量不同，可以分成单台机器的排序问题和多台机器的排序问题。对于多台机器的排序问题，按工件加工路线的特征，可以分成单件作业(Job-shop)排序问题和流水作业(Flow-shop) 排序问题。工件的加工路线不同，是单件作业排序问题的基本特征；而所有工件的加工路线完全相同，则是流水作业排序问题的基本特征。按工件到达车间的情况不同，可以分成静态的排序问题和动态的排序问题。当进行排序时，所有工件都已到达，可以一次对它们进行排序，这是静态的排序问题；若工件是陆续到达，要随时安排它们的加工顺序，这是动态的排序问题。按目标函数的性质不同，也可划分不同的排序问题。譬如，同是单台机器的排序，目标是使平均流程时间最短和目标是使误期完工工件数最少，实质上是两种不同的排序问题。按目标函数的情况，还可以划分为单目标排序问题与多目标排序问题。以往研究的排序问题，大都属于单目标排序问题，而对多目标排序问题则很少研究。
# Y1 E7 _  v% P另外，按参数的性质，可以划分为确定型排序问题与随机型排序问题。所谓确定型排序问题，指加工时间和其它有关参数是已知确定的量；而随机型排序问题的加工时间和有关参数为随机变量。这两种排序问题的解法本质上不同。