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

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

2、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 geneti

3、c algorithm（NSGA-II） 中图分类号：F273 文献标识码：A 文章编号：1006-4311（2016）33-0024-02 0 引言 1990 年 Bruker P 和 Schile R1首次提出了柔性作业车间调度问题2（FJSP） ，是传统作业车间调度问题的扩展。实际生产环境是动态的和随机的，如加工时间、设备故障和紧急插单等不确定因素都会对调度方案产生影响，而传统的确定情况下的调度问题的研究很难满足生产的需求。学者对不确定性因素扰动下的车间调度问题进行了研究。Baker K R（2014）2研究了单机机随机调度问题进行了研究，并假设加工时间服从正态分布。Palacios J

4、 J 等（2015）3提出一种将禁忌搜索和启发式规则相结合的遗传算法，用于求解加工时间不确定的柔性作业车间调度问题。丁雷等（2010）4研究了工时不确定条件下的车间调度问题。耿佳灿和顾幸生（2015）5研究了不确定条件下多产品间歇生产过程的调度问题，在调度问题中考虑了不确定的处理时间。 目前，常用求解 FJSP 的方法有标准遗传算法、禁忌搜索、粒子群算法、模拟退火法等智能算法。学者们也在不断探索用于求解 FJSP 更为有效的方法。Srinivas N 和 Deb K（1994）6提出非支配排序遗传算法（NSGA） ，算法采用分层方法使得优良的个体有更多机会进入下一代，采用小生境方法保持优秀个体

5、种群的稳定性及多样性，算法克服了标准遗传算法容易早熟这一不足。由于 NSGA 算法在应用过程中计算复杂度较高、没有精英策略以及需要人为指定共享参数，2002 年，Deb K 和 Pratap A7提出了第二代非支配排序遗传算法（NSGA-II） ，算法更适合求解FJSP 问题。 本文研究了随机工时下的 FJSP 问题。构建了随机工时下的柔性作业车间调度模型，并设计了用于求解调度问题的第二代非支配排序遗传算法。 31 问题描述和模型建立 1.1 调度问题描述 随机工时下的 FJSP 问题可以描述为：有 m 台机器和 n 个工件，工件 i 有 Ji 道工序，每个工件需要至少包含一道工序，工序先后顺

6、序是确定的，各道工序可以在不同的机器上加工，加工时间随着加工机器不同而变化，是一种随机变量。 1.2 前提假设 同一道工序在同一时刻只能在一台机器上加工；同一台机器同一时刻只能加工一道工序；所有工件在零时刻都可以被加工，工序一旦开始就不能中断；不同工件的优先级相同；同一工件的工序间有先后约束，不同工件工序间没有先后约束；各工序有多台可选的加工机器，且工序在机器上的理论加工时间已知，实际加工时间在给定范围内随机波动；各工序上相邻的两个加工工件之间无需切换时间。 2 研究方法设计 2.1 编码与解码 在编码过程中，染色体中基因数等于所有待加工工件工序的总数，每个基因表示一个工件号，工件号在染色体中

7、的出现的位置表示工件所对应的工序。编码的次序按照工件序号在染色体中出现的次序进行，从左向右扫描染色体的编码序列，当工件 i 第 j 次在编码序列中出现表示工件 i 第 j 道工序 Oij。解码是把编码的序列转化为调度问题可行解，按工序编码的顺序依次取出每一道工序，然后根据机器的分配方案，确定每道工序的最早开始加工时间。 2.2 精英策略 精英策略可以描述为：一个规模大小都为 N 的父代种群 Pt 和子代种群 Qt 合并形成规模为 2N 的种群 Rt，对种群 Rt 进行快速4非支配排序分层，并计算每一层个体的拥挤距离，最后根据个体的优劣程度从种群 Rt 中选择前 N 个个体形成新的父代种群。精英

8、策略将优秀的个体保留到下一代。 2.3 交叉操作 交叉操作是将种群中两个体随机部分或者是某些基因进行交换，从而产生新的基因组合的过程，交叉操作可以得到更为优秀的染色体。 基于工序顺序的交叉操作首先将所有待加工工件随机分成两个非空集合 J1 和 J2；然后将父代个体 P1 中包含在 J1 中的基因串复制到子代个体 C1 中，将父代个体 P2 中包含在 J2 中的基因串复制到子代个体 C2 中，并保持基因的位置不变，复制 P1 中包含在 J1 中的基因串保持先后顺序不变复制到子代个体 C2 中，复制 P2 中包含在 J2 中的基因串复制到子代个体 C1 中。 基于机器分配的交叉操作先产生一个由 0

9、、1 随机组成的集合 R，然后将父代 P1、P2 中与 R 集合中 0 位置相同的基因保留，而 1 位置的基因分别进行互换，交叉后得到两个子代 C1、C2。 2.4 变异操作 基于工序顺序的变异操作是随机选择任意一道工序，将它插入到一个任意的位置。而基于机器分配的变异操作是随机选择某个基因，用该工序可选机器集中的其他机器代替。 3 结语 本文对随机工时下的柔性作业车间调度问题进行了研究，建立了以最大完工时间为目标的调度模型，并设计了第二代非支配排序遗传算法（NSGA-II） 。随机工时下的 FJSP 问题更符合实际生产环境，对其研究具5有很大的应用价值。 参考文献： 1Brucker P， S

10、chlie R. Job-shop scheduling with multi-purpose machinesJ. Computing， 1990， 45（4）： 369-374. 2Baker K R. Minimizing earliness and tardiness costs in stochastic schedulingJ. European Journal of Operational Research， 2014， 236（2）： 445-452. 3Palacios J J， Gonzlez M A， Vela C R， et al. Genetic tabu searc

11、h for the fuzzy flexible job shop problemJ. Computers & Operations Research， 2015， 54： 73-89. 4丁雷，王爱民，宁汝新.工时不确定条件下的车间作业调度技术J.计算机集成制造系统，2010，16（01）. 5耿佳灿，顾幸生.不确定条件下中间存储时间有限多产品间歇生产过程调度J.化工学报，2015，66（1）：257-364. 6Srinivas N， Deb K. Muiltiobjective optimization using nondominated sorting in genetic algorithmmsJ. Evolutionary computation， 1994， 2（3）： 221-248. 7Deb K， Pratap A， Agarwal S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-IIJ. IEEE transactions on evolutionary computation， 2002， 6（2）： 182-197.