摘 要

本文主要针对准时制装配型作业车间调度问题展开研究。通过分析国内外的相关研究现状，本文分析了目前研究尚且存在的不足与空白。通过结合作业车间的实际情况，本文建立了以提前/拖期成本为目标函数的调度模型。同时，本文提出了运用LINGO软件的数学规划求解方法与结合局部搜索和遗传算法的启发式算法。在遗传算法求解过程中，本文提出了三步解码方法，从而有效提高了解码效率。

第二章简要介绍了作业车间调度问题的定义、特点与相关概念，并概述了常用于作业车间调度问题的求解方法。

第三章简要描述了作业车间调度问题，构建了相应的模型。并基于该模型，采用了LINGO软件对问题进行求解。

第四章针对准时制装配型作业车间调度问题求解复杂、实际问题规模可能较大的特点，采用遗传算法与局部搜索算法相结合的方法进行求解。并在遗传算法求解中提出了有效的三步解码方法。

第五章运用三、四章所提出的求解方法，针对设计的各组算例进行了求解。并针对遗传算法中的部分关键参数展开了讨论。最后，根据算例运行结果对LINGO求解和遗传算法求解这两种方法进行了分析与比较。

第六章针对本文中所展开的研究进行了简要的分析与总结，提出了本文尚且存在的不足，简单展望了今后的相关研究方向。

关键词：车间调度；准时制；遗传算法；数学规划；局部搜索

Abstract

This article focused on the scheduling problem of just-in-time assembly job shop. Through the analysis of the domestic and foreign research status, this paper analyzed the deficiencies and gaps of the existing research. Based on the actual situation of job shop, a scheduling model with earliness/tardiness cost as the objective function was established in this paper. At the same time, this paper proposed the mathematical programming solution method using LINGO software and the heuristic algorithm combining local search and genetic algorithm. In the solving process of genetic algorithm, this paper proposed a three-step decoding method, thus effectively improving the decoding efficiency.

The second chapter briefly introduced the definition, characteristics and related concepts of job shop scheduling problem, and summarized the solution methods commonly used in job shop scheduling problem.

The third chapter briefly described the job shop scheduling problem and constructd the corresponding model. Based on the model, LINGO software was used to solve the problem.

In chapter 4,genetic algorithm and local search algorithm were combined to solve the just-in-time（JIT）job-shop scheduling problem. An effective three step decoding method was proposed in the genetic algorithm.

In chapter 5, the solution method proposed in chapter 3 and chapter 4 was used to solve the designed examples. Some key parameters of genetic algorithm were discussed. Finally, the LINGO solution and the genetic algorithm solution were analyzed and compared according to the results of numerical examples.

The sixth chapter made a brief analysis and summary of the research in this paper, put forward the shortcomings of this paper,and briefly looked forward to the future research direction.

Key words：Job-shop scheduling；Just-in-time（JIT）；Genetic algorithm； Mathematical programming；Local search

目 录

第1章 绪论 1

1.1 论文研究背景与问题提出 1

1.2 国内外相关研究现状分析 2

1.3 论文研究的目的与意义 3

1.4 论文研究内容 3

1 5 论文结构及框架 4

第2章 作业车间调度问题的定义与求解方法 6

2.1 作业车间调度问题的相关概念与特点 6

2.2 作业车间调度问题的求解方法 8

第3章 基于准时化的作业车间调度模型 10

3.1 问题描述 10

3.2 基本假设 10

3.3 参数定义 11

3.4 目标函数建立 11

3.5 模型建立与求解 12

第4章 基于遗传算法的准时化车间调度问题的求解 14

4.1 编码方法 14

4.2 解码方法 15

4.3 个体重排 18

4.4 交叉操作 19

4.5 变异操作 20

4.6 改进遗传算法 20

4.7 选择操作 21

第5章 算例求解与结果分析 22

5.1 调度算例及实验环境 22

5.2 遗传算法实验设计 23

5.3 遗传算法相关参数讨论 25

5.3.1 交叉概率讨论 25

5.3.2 变异概率讨论 26

5.3.3 种群大小讨论 28

5.4 遗传算法灵敏度分析 29

5.4.1 交货期系数讨论 29

5.4.2 单位E/T成本系数比值讨论 31

5.5 遗传算法求解与结果分析 33

5.6 LINGO算例求解与结果分析 37

5.7 两种算法的分析与比较 38

第6章 总结与展望 40

参考文献 42

致 谢 44

第1章 绪论

本章主要论述了本文的研究背景、国内外研究现状、研究目的与意义以及本文的组织框架。

1.1 论文研究背景与问题提出

制造业是国家发展经济、稳定民生的重要基石。进入第四次工业革命时代，我国提出了“中国制造2025”战略。该战略旨在全球推行科技革命与智能化生产的形式下大力推进我国制造业结构变革，努力实现智能制造、提升制造业水平，将我国制造业不断向智能化、信息化、网络化推进。

随着智能制造的兴起和信息技术的发展，现代制造业正经历着由传统制造业向智能制造的转变。广泛运用人工智能技术和信息化手段的智能制造无疑将是制造业的未来发展方向。而作为制造业效益源泉的生产车间正是实现这一目标的重点控制对象。实现作业车间的合理调度是促进企业制造效率提高，实现企业利益持续增长的重要保证。

准时制生产方式（Just In Time，简称JIT），又称无库存生产方式、零库存生产方式等。JIT以准时生产为出发点，力求消除生产过程中的浪费及不必要的库存，在适当的时间将适当的物品送至适当的地方。虽然JIT中所追求的零库存模式是一种理想模式，很难在实际应用中实现。但准时化生产是制造企业追求的主要目标之一，同时也是企业低成本运营和精益化管控的重要手段^[17]。然而长期以来，由于生产周期不稳定、影响因素众多等原因，车间生产的作业调度往往难以实现准时化，从而导致了库存积压、延期交货等一系列问题，造成了企业的生产成本大大提高。本文正是立足于准时化生产的思想，以准时完工、准时交货为目标，在满足车间生产工序约束、机器约束等约束条件的基础上，寻求最优的作业车间调度方案。这一方案可以较好地满足企业以准时化生产为核心的生产思想，有效地减少企业生产成本，为企业实现有效控制作业调度、促进持续生产提供了较好的实践模拟与指导。

相关文献中指出，近年来有大量的文献针对作业车间调度问题展开研究，然而却极少有文章针对装配型车间调度问题开展研究^[3]。同时，这篇文献基于实际的企业生产情况，针对几种主流的调度规则展开了研究，并经过实验证明了主流的调度规则是适用于实际生产的，可以有效地帮助企业进行生产调度。这一文献也充分佐证了，合适的算法与调度规则可以有效地帮助企业减少成本、提高生产效率。本文中正是基于同样的目的，力求寻找到一种有效的算法以应用于企业的实际生产，帮助企业更好地进行生产调度。

1.2 国内外相关研究现状分析

本文所提出的面向准时化的作业车间调度正是将JIT思想运用于车间调度问题，将准时化交货作为衡量作业车间调度计划效率的主要指标，以达到促进各项作业准时完成，避免提前/拖期现象出现的目标。

目前针对作业车间调度问题展开的研究并不少，主要采取的解决方法有拉格朗日松弛法、遗传算法、神经网络算法、启发式方法等。作业车间调度问题已经被证实是一个典型的NP-hard问题^[8]。理论上而言，此类问题在时间和条件充分的情况下，可以求得最优解。然而，若采用枚举法或LINGO求解等方法，当作业复杂、工序众多时，求解难度及计算复杂程度将会呈指数级增长，难以在合理的时间内取得最优解。且在实际运用中，我们只需在合理的时间内取得较为良好的解即可。

自作业车间调度问题被提出后，众多学者围绕着该问题展开了各类研究。在问题研究初期，人们大多采用拉格朗日松弛法、线性规划等传统约束规划方法。随着人们对于该问题认识的深入，遗传算法、神经网络算法等启发式方法逐渐进入人们的视野，并被广泛运用在作业车间调度问题上。近年来，多位学者对于车间调度问题的研究都是在启发式算法的框架下展开的，并取得了良好的成果。

其中遗传算法是被采用得较多的求解方法。根据知网统计数据显示，在知网的相关文献中，遗传算法的使用率高达11.54%。同时，粒子群算法、模拟退火算法、蚁群算法、多目标算法等也被多次运用于车间调度问题的求解中。近年来，为了进一步提高求解效率，避免结果陷入局部最优解，改进遗传算法和启发式算法逐渐得到了人们的认可，成为了作业调度问题的主流解决方法。

姚伟力等基于模糊控制和遗传算法，提出了求解作业车间（Job-shop）提前/拖期问题的联合算法^[20]。Baptiste首次在车间作业调度问题中引入了工序交货期的概念，以提前成本和拖期成本作为目标函数构建了工序级提前/拖期调度模型，并采用拉格朗日松弛法与领域搜索算法相结合的方式求得了可行的调度解^[8]。Araujo等采用遗传算法求得提前/拖期调度问题的近似最优解，并提出了一种有效的局部搜索方法，以针对遗传算法给出的解进一步探索最优解^[1]。李海宁针对传统E/T调度问题忽视零件最晚可接受时间（deadline）的问题，建立了带有零件deadline约束的优良制造中心E/T/D调度模型^[12]。王荪馨将遗传算法与子集选择方法相结合，从而预先过滤掉了调度解性能相对较差的个体，并对剩余解集进行了精细仿真与评估，有效解决了寻优空间过大的问题^[17]。赵诗奎等针对最小化最大完工时间的作业车间调度优化问题，在比较了多种调度规则的基础上，提出了一种基于工序间空闲时间的领域搜索遗传算法^[22]。姚远远等通过基于工序编码，采用了一种新型元启发式算法——布谷鸟算法对作业车间调度问题进行了布谷鸟搜索算法求解^[21]。Goncalves提出了基于新领域结构的随机键遗传算法，并给出了57个基准实例的目前最优解^[5]。

总体而言，我们可以发现，采用智能算法求解作业车间调度问题是一种行之有效的方法。然而，现有研究中大多数是针对流水线准时化作业进行求解，而显少有涉及装配型车间调度问题的。同时，大多数研究都是采用改进型遗传算法进行求解，而忽视了遗传算法存在的局限性。本文可以针对现有研究中存在的不足和缺陷，采用局部搜索与遗传算法相结合的方法，针对装配型调度问题进行求解，从而弥补现有研究中的空白。

1.3 论文研究的目的与意义

制造业作为我国国民经济的重要组成成分，在推动我国经济发展、促进我国经济转型上有着不可替代的重要作用。随着智能制造的兴起，如何将制造业更好地与信息化技术、智能化生产相结合逐渐成为了制造业的一大核心问题。作为制造业成本控制与生产控制的重点，生产车间的重要问题——调度问题也逐渐得到了人们的普遍重视。

目前，大多数的研究仍是针对单机作业调度问题而展开的。Baker 和Sudder针对该问题做出了比较全面的阐述与分析，并简要介绍了常用于解决这类问题的方法^[6]。然而，现今极少有针对于并行机问题的作业车间调度问题研究，面向装配型生产车间的作业车间调度问题的研究更是凤毛麟角。实际上，装配型作业车间调度问题的约束条件虽然相比单机作业调度问题显得更为复杂，但却与大多数企业的实际加工生产情况更为相符，也更具实际操作意义与指导意义。

另一方面，准时化生产是制造企业所追求的重要目标之一。在装配型车间的准时化调度问题中，产品的提前完工会导致库存积压、资源浪费，从而极大地提高了企业的生产成本，进一步影响了企业的生产调度。而产品的延期完工则会导致工期延误，从而影响后期的生产调度，也会造成企业的利润与信誉下降。

本文正是针对装配型企业的作业车间调度问题，将装配型车间的实际生产情况抽象为数学问题，以准时化生产为目标，在遵循机器约束、工序约束等约束条件的基础上，寻求使得目标最优化的调度计划。该研究与实际情况较为相符，对于制造企业而言有着更好的指导意义与实际运用意义。该方法不仅可以帮助企业降低生产成本，实现准时化生产，也可以帮助企业稳定生产调度与生产质量，提高企业的生产控制水平与销售信誉。

1.4 论文研究内容

正如上文所阐述的，本文是围绕装配型车间的准时化作业车间调度问题而展开的。本文的主要研究内容如下：

1）阐述面向准时交货的作业车间调度问题

简要分析了作业车间调度问题的国内外研究现状，介绍了作业车间调度问题。并结合JIT思想解释了面向准时交货的作业车间调度问题的意义与实际运用价值，简介了常用于该问题的各类典型算法与思想。

2）建立数学规划模型

根据准时化思想构建传统的数学规划模型，简要介绍该模型，同时利用LINGO软件构建以提前/拖期成本为目标函数的作业车间调度模型，并求解。

3）简介本文的算法思想与求解

遗传算法是现今最常用于求解作业车间调度问题的算法之一。采用遗传算法与局部搜索算法相结合可以有效避免调度解陷入局部最优解的问题。采用遗传算法求得作业车间调度问题的近似最优解，并采用局部搜索算法对遗传算法求得的解进行进一步的局部寻优。建立相应的问题模型，编写相应的算法代码，利用软件编码进行求解。最后将两种上述两种方法求得的解进行比较分析。

1 5 论文结构及框架

本文一共分为五章。

第一章介绍了本文的研究背景、研究内容、目的与意义，并简要介绍了国内外的相关研究现状。

第二章给出了作业车间调度问题的定义，结合JIT思想介绍了面向准时交货的作业车间调度问题，介绍分析了近年来常用于解决作业车间调度问题的算法。

第三章采用传统的数学规划方法建立了以准时化为目标，遵循机器约束、工序约束等约束的数学模型，采用LINGO进行了求解。

第四章介绍了遗传算法与局部搜索算法在作业车间调度问题中的主要应用。简要阐述本文中的算法思想与求解思路。

第五章基于第三、四章的求解思路进行编码求解。通过多次实验调整算法参数，运行多组数据进行灵敏性分析与求解。并将两种方法的求解结果进行分析与比较。

第六章总结了全文，反思本文中可能存在的缺陷与不足，并展望了未来的求解方向与问题应用。

本文的研究框架如图1.1所示。

图1.1　本文研究框架

第2章 作业车间调度问题的定义与求解方法

本章简要介绍了作业车间调度问题的定义、特点与相关概念，并概述了常用于作业车间调度问题的求解方法。

2.1 作业车间调度问题的相关概念与特点

车间调度问题实际上是组织执行生产进度计划中的问题，涉及到加工顺序的安排、加工时间的确定、加工机器的安排等问题。企业为了合理安排生产往往会编制生产计划和生产作业计划。在生产计划和生产作业计划编制完成后，为将计划落实到具体的生产过程中，则需编制物料需求计划（MRP）。而生产调度就是将物料需求计划落实至生产任务管理当中。作业车间调度问题实际上就是生产调度中的核心问题。

作业车间调度问题（Job-shop scheduling problem，JSP）是最基本、最著名的调度问题，也是一个经典的NP-hard问题，目前还没有可以求得其最优解的精确算法。按照机器数分类，单车间调度问题可以进一步分为单机调度问题和多机调度问题。单机调度问题是最基础的单车间调度问题，仅需考虑工件在一台机器上的加工顺序，无需考虑机器约束问题。多机调度问题则是存在多台加工机器，不同的工序需要在不同的机器上进行加工，需要考虑的约束也更为复杂。本文中的调度问题正是一个多机调度问题。