Job Shop Schedule 生产调度问题

生产调度的研究主要可分为建模和调度算法设计两方面，它是一个交叉性研究领域.涉及运筹学，数学，计算机工程，控制工程，工业工程等多个学科。 其中，建模主要研究调度模型，调度规则，目标函数等内容：算法主要研究算法设计，算法复杂性，算法收敛性和优化质量等内容。对于m台机器(machine)对n个工件job的加工过程，所谓调度就是分配各工件在各机器上的加工时间。调度通常用上甘特图(Gantr chart)表示.图为4个工件3台机器的面向机器的甘特图和相应的面向工件的甘特图。

生产调度问题的分类方法有很多种，根据不同的分类标准，有着不同的分类方式。一般来讲，主要的分类方式有以下几种:

• 根据生产方式的不同，可分为开放车间(open shop)和封闭车间(closed shop ) 。开放车间中没有库存，客户需求什么样的产品，就现场加工生产提供给客户;封闭车间中有很多库存产品，客户需求多少产品，可以直接从库存中取货，然后调度者再根据库存量来安排相应的生产。
• 根据生产系统复杂性的不同，可分为单机调度、并行机调度、流水车间调度(flow shop)和作业车间调度(job shop ) 。各种调度类型之间的具体关系如图所示。
• 根据调度目标的不同，可分为基于调度成本和基于调度性能两类。常见的基于调度成本的目标有最小化生产成本、运输成本、存储成本等;基于调度性能的目标有最小化最大完工时间、总拖期时间等。

车间调度问题的描述

Job Shop调度问题是企业生产活动中最常见的复杂车间调度问题，是许多实际生产调度问题的简化模型，是一个典型的NP-hard问题。JobShop调度问题研究n个工件在m台机器上的加工，已知各操作的加工时间和各工件在各机器上的加工次序约束，要求确定与工艺约束条件相容的各机器上所有工件的加工开始时间或完成时间或加工次序，使加工性能指标达到最优。

在典型的Job shop调度问题中，除了技术约束外，通常还假定以下条件：

• 整个加工过程中，一个工件不能在同一台机器上加工多次;
• 任何一个工件的前一道工序加工完成后，方能进行后一道工序的加工，在同一台机器上一个加工任务完成之后，方能开始另一个加工任务;
• 各工件必须按工艺路线以指定的次序在机器上加工;
• 不考虑工件加工的优先权;
• 每个工件的工序一旦进行就不能中断;
• 一个工件同一时间只能在一台机器上加工，一台机器同一时间只能加工一个工件，加工的开始时间为0。

另外，调度还必须满足工件的工艺约束条件和资源占用约束，两类约束条件描述如下：

    (1) 工艺约束

(2)资源约束

析取图也是描述JSP的常用工具。对于n个工件、m台机器(共N个操作)的JSP，所对应的析取图如图所示。图中，V为所有操作构成的顶点集，包括。和N+1两个虚拟操作(分别表示加工开始和结束);A为n条子边构成的边集，子边(实线)表示某个工件按约束条件在所有机器上从开始到结束的加工路径;E为m条子边构成的弧集，子弧(虚线)表示同一机器上加工各操作的连接。若以最大完成时间为指标，则对JSP的求解就归结为找到各弧(即机器)上作为优先决策的各操作的一组顺序(即走向)，当同一机器上有多个操作出现冲突时，上述顺序用于决定各操作的先后，最终得到各操作时间没有冲突的一个有向非循环图，而其关键路径长度即为最大完成时间。

工件3机器的析取图

参考文献：

[1]  黄英杰, 基于目标级联法和智能优化算法的车间调度问题研究[D], 华南理工大学 ，2012.

[2] 崔喆，基于群智能优化算法的流水车间调度问题若干研究[D],华东理工大学，2013