随机工时下的柔性作业车间调度问题研究

摘要： 本文研究了随机工时下的柔性作业车间调度问题。对随机工时下的柔性作业车间调度问题进行描述，构建了以最大完工时间为优化目标的调度模型，并设计了第二代非支配排序遗传算法（NSGA-II）求解调度问题。

Abstract： In this paper， flexible job shop scheduling problem with random working time is studied. The flexible job shop scheduling problem with random working time is described. The scheduling model with the maximum completion time is constructed and the second-generation non-dominated sorting genetic algorithm （NSGA-II） is designed to solve the scheduling problem.

关键词： 随机工时；柔性作业车间；非支配排序遗传算法（NSGA-II）

Key words： random work time；flexible job shop；non-dominated sorting genetic algorithm（NSGA-II）

中图分类号：F273 文献标识码：A 文章编号：1006-4311（2016）33-0024-02

0 引言

1990年Bruker P和Schile R[1]首次提出了柔性作业车间调度问题（FJSP），是传统作业车间调度问题的扩展。实际生产环境是动态的和随机的，如加工时间、设备故障和紧急插单等不确定因素都会对调度方案产生影响，而传统的确定情况下的调度问题的研究很难满足生产的需求。学者对不确定性因素扰动下的车间调度问题进行了研究。Baker K R（2014）[2]研究了单机机随机调度问题进行了研究，并假设加工时间服从正态分布。Palacios J J 等（2015）[3]提出一种将禁忌搜索和启发式规则相结合的遗传算法，用于求解加工时间不确定的柔性作业车间调度问题。丁雷等（2010）[4]研究了工时不确定条件下的车间调度问题。耿佳灿和顾幸生（2015）[5]研究了不确定条件下多产品间歇生产过程的调度问题，在调度问题中考虑了不确定的处理时间。

目前，常用求解FJSP的方法有标准遗传算法、禁忌搜索、粒子群算法、模拟退火法等智能算法。学者们也在不断探索用于求解FJSP更为有效的方法。Srinivas N和Deb K（1994）[6]提出非支配排序遗传算法（NSGA），算法采用分层方法使得优良的个体有更多机会进入下一代，采用小生境方法保持优秀个体种群的稳定性及多样性，算法克服了标准遗传算法容易早熟这一不足。由于NSGA算法在应用过程中计算复杂度较高、没有精英策略以及需要人为指定共享参数，2002年，Deb K 和Pratap A[7]提出了第二代非支配排序遗传算法（NSGA-II），算法更适合求解FJSP问题。

本文研究了随机工时下的FJSP问题。构建了随机工时下的柔性作业车间调度模型，并设计了用于求解调度问题的第二代非支配排序遗传算法。

1 问题描述和模型建立

1.1 调度问题描述 随机工时下的FJSP问题可以描述为：有m台机器和n个工件，工件i有Ji道工序，每个工件需要至少包含一道工序，工序先后顺序是确定的，各道工序可以在不同的机器上加工，加工时间随着加工机器不同而变化，是一种随机变量。

1.2 前提假设 ①同一道工序在同一时刻只能在一台机器上加工；②同一台机器同一时刻只能加工一道工序；③所有工件在零时刻都可以被加工，工序一旦开始就不能中断；④不同工件的优先级相同；⑤同一工件的工序间有先后约束，不同工件工序间没有先后约束；⑥各工序有多台可选的加工机器，且工序在机器上的理论加工时间已知，实际加工时间在给定范围内随机波动；⑦各工序上相邻的两个加工工件之间无需切换时间。

2 研究方法设计

2.1 编码与解码 在编码过程中，染色体中基因数等于所有待加工工件工序的总数，每个基因表示一个工件号，工件号在染色体中的出现的位置表示工件所对应的工序。编码的次序按照工件序号在染色体中出现的次序进行，从左向右扫描染色体的编码序列，当工件i第j次在编码序列中出现表示工件i第j道工序Oij。解码是把编码的序列转化为调度问题可行解，按工序编码的顺序依次取出每一道工序，然后根据机器的分配方案，确定每道工序的最早开始加工时间。

2.2 精英策略 精英策略可以描述为：一个规模大小都为N的父代种群Pt和子代种群Qt合并形成规模为2N的种群Rt，对种群Rt进行快速非支配排序分层，并计算每一层个体的拥挤距离，最后根据个体的优劣程度从种群Rt中选择前N个个体形成新的父代种群。精英策略将优秀的个体保留到下一代。

2.3 交叉操作 交叉操作是将种群中两个体随机部分或者是某些基因进行交换，从而产生新的基因组合的过程，交叉操作可以得到更为优秀的染色体。

基于工序顺序的交叉操作首先将所有待加工工件随机分成两个非空集合J1和J2；然后将父代个体P1中包含在J1中的基因串复制到子代个体C1中，将父代个体P2中包含在J2中的基因串复制到子代个体C2中，并保持基因的位置不变，复制P1中包含在J1中的基因串保持先后顺序不变复制到子代个体C2中，复制P2中包含在J2中的基因串复制到子代个体C1中。

基于机器分配的交叉操作先产生一个由0、1随机组成的集合R，然后将父代P1、P2中与R集合中0位置相同的基因保留，而1位置的基因分别进行互换，交叉后得到两个子代C1、C2。

2.4 变异操作 基于工序顺序的变异操作是随机选择任意一道工序，将它插入到一个任意的位置。而基于机器分配的变异操作是随机选择某个基因，用该工序可选机器集中的其他机器代替。

3 结语

本文对随机工时下的柔性作业车间调度问题进行了研究，建立了以最大完工时间为目标的调度模型，并设计了第二代非支配排序遗传算法（NSGA-II）。随机工时下的FJSP问题更符合实际生产环境，对其研究具有很大的应用价值。

参考文献：

[1]Brucker P， Schlie R. Job-shop scheduling with multi-purpose machines[J]. Computing， 1990， 45（4）： 369-374.

[2]Baker K R. Minimizing earliness and tardiness costs in stochastic scheduling[J]. European Journal of Operational Research， 2014， 236（2）： 445-452.

[3]Palacios J J， González M A， Vela C R， et al. Genetic tabu search for the fuzzy flexible job shop problem[J]. Computers & Operations Research， 2015， 54： 73-89.

[4]丁雷，王爱民，宁汝新.工时不确定条件下的车间作业调度技术[J].计算机集成制造系统，2010，16（01）.

[5]耿佳灿，顾幸生.不确定条件下中间存储时间有限多产品间歇生产过程调度[J].化工学报，2015，66（1）：257-364.

[6]Srinivas N， Deb K. Muiltiobjective optimization using nondominated sorting in genetic algorithmms[J]. Evolutionary computation， 1994， 2（3）： 221-248.

[7]Deb K， Pratap A， Agarwal S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-II[J]. IEEE transactions on evolutionary computation， 2002， 6（2）： 182-197.