摘 要

混合流水车间调度问题也称柔性流水车间调度问题，是经典流水车间调度问题和并行机调度问题的结合。相比之下，混合流水车间调度问题要求在整个加工流程中，至少有一个阶段含有两台及以上的并行机器，属于较为复杂的NP-Hard难题。在传统的调度理论研究中，待加工任务的加工时间通常被看作是固定且已知的离散量，而在现实生产环境中，通过对加工过程中所消耗的一定数量的额外资源的分配，可以实现对任务加工时间的控制。可控加工时间的引入，能够减少调度理论研究与现实生产应用之间的差异，同时增加调度的灵活性。目前，有关可控加工时间的调度研究主要停留在单机环境下，与实际的应用需求相比，仍有较大差距，因此本文的选题具有一定的理论研究意义及较高的工程应用价值。

针对目前国内外混合流水车间调度的研究现状，本文重点研究了加工时间可控的混合流水车间调度问题。首先对混合流水车间调度问题的基本理论、特点与发展状况进行了综述；然后介绍了遗传算法的基本思想和求解方法；其次，以最小化最大完工时间为目标建立了混合流水车间调度问题的数学模型，初始化种群的可控时间加工范围，采用基于矩阵的二维编码方式，设计了用遗传算法求解带可控加工时间的混合流水车间调度问题的流程；最后利用MATLAB软件进行了实例仿真，通过调整各道加工操作的时间参数，输入压缩后的实际加工时间，得到对应的最优调度方案，并开发出原型系统，验证了遗传算法求解加工时间可控的混合流水车间调度问题的有效性。

关键词:混合流水车间调度；加工时间可控；遗传算法

Abstract

The hybrid flow shop scheduling problem is also called flexible flow shop scheduling problem, which is a combination of general flow shop scheduling problem and parallel machine scheduling problem.Hybrid flow shop scheduling problem, by contrast, requirement in the machining process, at least one stage with two or more parallel machine, belonging to the more complex NP - Hard problem. In the study of traditional scheduling theory, machining time of task is usually seen as a fixed and known discrete quantity, in the real production environment, task processing time can be through the distribution and consumption in the process of machining a certain number of additional resources to control them. The introduction of controllable task processing time can reduce the scheduling the difference between theoretical research and practical production application, at the same time increase the flexibility of the scheduling algorithm. At present, the studies of controllable processing times of scheduling problem mainly stay in LAN environment, compared with the actual application requirements, there is still a large gap, so this topic has theoretical research significance and engineering application value.

In view of the present and the research status of hybrid flow shop scheduling at home and abroad, this article focuses on the task of hybrid flow shop scheduling problem with controllable processing. First of all, the basic theory and characteristics of hybrid flow shop scheduling problem and development situation are discussed; Then introduces the basic idea and algorithm of genetic algorithm; Second, to minimize the maximum completion time, a mixed integer programming model is established with the target of initialization population of controllable processing time range, the two-dimensional coding method based on matrix, designed a genetic algorithm to solve the hybrid flow shop scheduling problems with controllable processing times of the process; Finally the use of MATLAB software for instance simulation, by adjusting the time parameters of each process operating input the actual processing time of compressed, get the corresponding optimal scheduling scheme and developed the prototype system, genetic algorithm is verified hybrid flow shop scheduling problem with controllable processing is effective.

Key words: Hybrid flow shop scheduling;Controllable processing times;Genetic Algorithm

目录

摘 要 I

Abstract II

第1章 绪论 1

1.1课题来源 1

1.2论文的研究目的及意义 1

1.3国内外研究的发展及现状 2

1.3.1混合流水车间调度问题研究现状 2

1.3.2加工时间可控的调度问题研究现状 2

1.4本文的主要工作与结构 3

第2章 混合流水车间调度问题概述 4

2.1车间调度问题的描述 4

2.2混合流水车间调度的基本理论 4

2.2.1混合流水车间调度问题的描述 5

2.2.2混合流水车间调度问题的分类 5

2.2.3混合流水车间调度问题的特点 6

2.3加工时间可控的调度问题 6

第3章 遗传算法概论 8

3.1遗传算法的基本思想 8

3.2遗传算法的基本步骤 8

3.3遗传算法的特点 10

第4章 带有可控加工时间的混合流水车间调度 12

4.1 HFSP数学模型 12

4.1.1符号说明 12

4.1.2决策变量 12

4.1.3目标函数和约束条件 12

4.2 基于遗传算法的求解方法 13

4.2.1编码方式 13

4.2.2初始种群的生成 14

4.2.3适应度函数 15

4.2.4选择 15

4.2.5交叉 15

4.2.6变异 16

第5章 HFSP-CPT遗传算法实现 17

5.1实际案例分析 17

5.1.1标准加工时间 17

5.1.2实际加工时间范围确定 17

5.2实例调度GUI仿真界面设计 19

第6章 总结与展望 24

6.1全文总结 24

6.2研究展望 25

参考文献 26

附 录 28

致 谢 44

第1章 绪论

在大规模复杂的当代生产系统中，如何经营管理、组织生产成为决策者关注的重点。车间调度是生产调度的重要组成部分，合理的车间调度不仅可以提高生产效率，降低生产成本，还可以为车间外部的活动计划提供准确的相关信息。对车间调度的研究成果不仅可以指导实际生产，还可以推广到其他涉及资源分配的领域。因此，对车间调度问题的研究具有重大的理论意义和现实意义。混合流水车间调度问题是一类重要的车间调度问题，在实际生产中有广泛的应用，尤其是在制造业和装配业，因此一直是生产管理者和调度理论研究者关注的重点。

1.1课题来源

本文的课题来源为国家自然科学基金重点项目，“大数据驱动的智能车间运行分析与决策方法研究”（51435009），2015.1-2019.12.

1.2论文的研究目的及意义

在传统的调度问题研究中，通常认为任务具有固定且已知的加工时间^[1]。调度算法的目标，是合理安排任务在不同的机床上，按照一定的顺序依次进行加工。然而，在大量的现实生产活动中，任务往往具有在一定范围内长度不定且可以得到控制的加工时间。通过向生产活动中投入额外的资源，如人力、燃气、电力，以及资金预算等，通常能够提高生产速度，压缩任务的加工时间。显然，通过增加对任务加工时间的控制，调度算法能够产生出更加贴近于现实需求的生产计划，帮助生产商提高生产管理质量，降低生产成本，提升核心竞争力。

在混合流水车间调度问题中，任务之间存在有一定的加工顺序约束条件。加工顺序约束条件下的调度问题具有显著的现实意义。一件产品，例如一辆汽车，通常由大量的零部件组成，而这些零部件的加工，又往往根据生产工艺的要求，具有先后的加工顺序。简单的零件构成了较为复杂的部件，较为复杂的部件构成了更加复杂的部件，如此自底向上直至组装为最终产品。但是，受限于加工顺序约束所带来的计算复杂性，在任务加工时间可控条件下尚未见到这类混合流水车间并行加工调度问题的研究成果。