关键词:遗传算法车间调度交叉变异

原文

背景及摘要：

调度问题具有相当的难度，目前调度问题的理论研究成果主要在集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。求解调度问题的方法统称为调度优化算法，它可分为精确求解方法和近似求解方法。其中精确求解方法包括解析方法、穷举方法（包括分支定界）等；近似求解方法包括基于规则的构造性方法、邻域搜索算法（如进化遗传算法，模拟退火算法）以及人工智能方法（如神经网络）等。而传统的运筹学方法，即便在较大规模的基于单目标优化的静态调度问题中也难以有效应用。

本文从实际和理论两方面进行研究和深入，重点研究了现代进化算法中有代表性发展优势的遗传算法，通过MATLAB软件，实现对该算法的计算机模拟以及对其优化方案的研究性分析。

一．问题重述

生产计划安排：

某重型机械厂产品都是单件性的，其中有一车间共有A，B，C，D四种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加工，其工序与加工周期如下表：（S-设备号、T-周期）

工序产品12345678

STSTSTSTSTSTSTST

1C8A2B4C24D6

2A4D5B3C4

3C3D7A15B20A8

4B7C6D21A1D16C3

5D10B4C8D4A12C6D1

6A1B4A7C3D5A2C5A8

(表一)

条件：1、每件产品必须按规定的工序加工，不得颠倒。

2、每台设备在同一时间只能担任一项任务。

目录

一．问题重述

二．问题分析

三．模型假设

四．符号说明及初始数据表达分析

五．贪婪法快速求解

六．计算机随机模拟（编程）

七．遗传算法模型建立和步骤解法

八．计算机模拟的实现（用MATLAB工具编程）

九．遗传算法模拟结果

十．模型优缺点及改进

参考资料

1．车间调度与遗传算法王凌清华大学出版社

2．数值计算的算法与分析张可村赵英良科学出版社

3．PermutationBasedGAsandOrderedGreedPeterG.Anderson,

4．MATLAB6.0王沫然电子工业出版社

5．C程序设计（第二版）潭浩强清华大学出版社