[科普中国]-日程表问题

日程表问题(scheduling problem)亦称调度问题，是一类组合优化问题，对于一个给定的活动计划确定各项活动的进行的时间段，使得预先选定的目标函数取最小值，这个目标函数常取为最终完成时间的一个非降函数，若要有资源的限制，还可以在保证完成时间之下使得资源的总花费为最小1。

基本介绍日程表问题即对于一个给定的活动计划确定各项活动的进行的时间段，使得预先选定的目标函数取最小值。日程表问题的一个典型实例就是排序问题。另外，还有项目日程表问题和装配线平衡问题。项目日程表问题，也称统筹方法。

项目日程表问题项目日程表问题，也称统筹方法，是用数学方法对计划进行组织安排与协调管理的一种工具。它是用网络图的形式把计划的各个部分形象地组成一个整体，直观地显示出计划各个环节之间错综复杂的依存关系，并给予量的描述，便于领导机关和计划管理人员统筹兼顾，全面安排2。

基本步骤如下：

1.编制网络图，把整个任务根据工艺上与组织上的内在联系分解为若干个工序，然后根据工序先后顺序和相互关系，列出工序清单，标明工序代号，并注明各工序的紧前工序和紧后工序。根据这些，就可以从第一道工序开始，以一条箭线代表一个工序，工序的两端是两个结点，顺序地从左至右依次画下去，直到最后一道工序。每道工序用(i，j)表示，i，j分别是这道工序的开始结点和终点结点。

2.计算各种数据：结点的最早开工时间是表示完成工序(i，j)所需要的时间。从始点开始自左向右逐个计算直到最后一个结点止。

结点最迟完成时间是，从终点开始，自右向左逐个计算。

结点的时差是。然后再计算工序的最早开始时间、最早完成时间、最迟开工时间、最迟完成时间和总时差。把总时差等于零的工序依次串联起来，就是关键路线。

3.利用网络图和计算出来的数据、关键路线来对计划进行组织、协调和控制。概括起来，有下列三方面的内容：抓主要矛盾，缩短关键工序时间，加速计划进度;根据各工序所需要的原材料、设备、劳动力和资金，在上述资源限制的条件下，如何统筹安排、综合平衡、提高资源利用率;由于时间紧迫，必须加快计划进度，但又要做到经济上合理，使工程计划的成本费用最低2。

装配线平衡问题在流水装配中，根据分工原则制定的各站位工作量大致平衡，每个工人在他的工位上做指定的工作项目 (工序)单元。当每一项目单元经过该站站 位时，工人对其重复操作，这就要求工业工程师对每一站位上的工作时间进行平衡，防止发生等待或 堆积现象，充分发挥和利用装配线的功能。

装配线平衡问题，我们可以接受下述定义：“在规定的装配线速度下，使总的空闲时间最少，或使做一额定工作量的操作人数最少，从而保证平衡延 迟最少”。这里平衡延迟是指整个装配线上各站位总空闲时间量。可用下式表示：

对某一具体产品的装配线系统造成高平衡延 迟的主要原因是由于给定的站位时间Nt差别大， 大量非柔性的装配线机械和不加区别地无科学根据的选择站位时间。当然站位时间常由一具体的所希望的生产率决定，但并不会导致低的平衡延迟。

可以理解，装配线上不会绝对的平衡，为了保证装配线较低的总平衡延迟，工业工程师应科学合 理的分派工位工序及站位人数，调节工艺流程和确 定站位与工位、工序时间。

装配线平衡是一个复杂的系统工程，它涉及到工厂的计划管理、生产管理、工艺技术管理、工时 管理、成本管理，以及各种资源的管理与使用。大 型制造装配项目的各种管理更加复杂。但任何作 业，无论多么复杂都能分解为一系列简单的作业， 使我们直接或间接地找到解决问题的许多办法。这 其中大量的是一般性问题，而真正复杂的问题仅占 一小部分。收集和分析一个复杂作业的信息，最符合逻辑的方法是仔细检查构成要素。全面地了解这 些，可以阐明全部复杂问题，清楚地识别和分离出那些在管理上需要特别注意的例外问题。为此，在装配线平衡设计中要考虑如下要素：

产品——分解结构;

目标——累积交货进度;

项目——生产计划;

项目进展——执行现状;

项目进展与目标的比较——平衡;

装配周期图——带有时间的装配流程图。

产品分解结构即把构成产品主体的各元素分 解成各子项，这一层层分解的过程，要使项目分解 到既符合装配逻辑又易于管理控制的水平。在计划 阶段“分解结构”作为框架用来概括“由下而上”的 信息。这样能满足任何装配线设计层次上的决策要 求，为获得各站位的平衡打下框架基础。

目标是指生产过程的目标，其目的是在装配线 平衡设计中，依据供货合同保证累积交货进度。

项目是指生产计划。它是根据作业和站位推出 装配计划或“装配周期图”。装配线站位时间的提前 期与最终完工期的关系是装配线平衡中最重要的 阶段，是装配循环站位周期中最重要的步骤，可以 用来监督装配向最终完工状态发展的中间过程。

装配周期图是通过收集和详细研究而产生出 来的反映装配顺序、各作业之间的衔接关系、所占 周期的一种图表。装配周期图可使工业工程师在调 整装配线平衡时一目了然地进行站位、工位的调 整，以协调站位时间的一致，并合理确定站位操作人员数量3。

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所