摘 要

批调度问题，现已成为一种新型的调度问题，近些年来引起研究者的热切讨论。本文针对铸造车间差异工件组批多约束的问题，本文在工序可并行加工的前提下构建了以最大完工时间和沙箱空置率为优化目标的并行工序批调度模型。设计了一种改进和声算法求解该调度模型，提出了一种单工序编解码方式和两种机器分配规则用于解决工件批次划分、沙箱选择、工序分配及机器选择问题。在算法中提出了一种新和声产生方式和更新机制，同时在局部搜索阶段加入模拟退火算法，可以使得到的解具有趋于全局最优解的能力，并对算法跳出局部最优解的能力有了提高。然后将本文模型结合企业具体的生产数据来进行仿真实验，为企业制定具体的调度方案并检验方案是否为最优。最后，对本文的研究进行分析概述，并对未来此领域的相关问题作出展望。

关键词：差异工件；工序并行；批调度；多约束；和声搜索算法；

Abstract

Batch scheduling problem, which has become a new scheduling problem, has been hotly discussed by researchers in recent years. In view of the situation of multi-constrained in the batch process with Non-identical job sizes in Foundry Enterprises，this paper constructs a parallel process batch scheduling model with the maximum makespan and sandbox vacancy rate as the optimization objective on the premise that the job can be parallel. An improved harmony search algorithm is designed to solve the scheduling model. A single process codec method and two machine allocation rules are proposed to solve the problems of batch division, Sandbox selection, process allocation and machine selection. In the algorithm, a new harmony generation method is proposed.At the same time, the simulated annealing algorithm is added in the local search stage, which can make the solution tend to the global optimal solution and improve the ability of the algorithm to jump out of the local optimal solution. Then, this model is combined with the specific production data of the enterprise to carry out simulation experiments, to develop specific scheduling scheme for the enterprise and test whether the scheme is optimal. Finally, this paper analyzes and summarizes the research of this paper, and makes a prospect of the related issues in this field in the future.

Key words：Non-identical Job Sizes；Process parallel; Batch scheduling; multi-constrained; Harmony Search algorithm;

目录

第1章 绪论 1

1.1引言 1

1.2国内外研究现状 2

1.3研究内容及结构规划 2

1.3.1本文的研究内容 2

1.3.2本文的结构规划 3

第2章 数学模型的构建 4

2.1问题描述 4

2.1.1参数定义 4

2.1.2问题假设 5

2.1.3决策变量 6

2.1.4数学模型 6

第3章 和声算法的设计 8

3.1和声搜索算法简介 8

3.2算法设计 8

3.2.1编码与解码 8

3.2.2机器分配规则 10

3.2.3交换算子和插入算子 10

3.3 算法流程 11

3.3.1全局搜索阶段 11

3.3.2局部搜索阶段 12

第4章 案例仿真与应用 14

4.1实验设计 14

4.2参数设置 15

4.3实验结果与分析 16

4.4本章小结 19

第5章 总结与展望 20

5.1全文总结 20

5.2工作展望 20

参考文献 21

致谢 23

第1章 绪论

1.1引言

现今科技和生产能力持续进步，制造业在国家实体经济中越来越重要，现已经发展为中国经济的重要支柱。随之而来，各个企业也将应对新的挑战与机会。在市场竞争日益激烈条件下，一个企业想要蓬勃发展的根源则是具备完备的生产理论知识、先进的生产管理模式、灵活的反应能力。而调度问题更是企业生产中重要的环节。调度是将多个任务中的有限的资源进行合理的安排分配，使企业所要达到的目标最优。在于系统规划对有限的生产资源进行系统规划是调度问题的本质，在已经确定的规则下合理安排生产流程以确保目标最优化。合理的调度对企业在生产过程的监管和控制方面产生巨大影响，进而影响企业的竞争能力。

调度已经成为工程方面的热度问题，各领域的研究者从不同的角度对调度问题进行了广泛且深入的讨论。随着计算机领域的不断发展和制造加工技术的日渐成熟，调度系统现已更加普遍和深入的用在制造邻域。在制造业中，生产调度问题现已经成为企业的生产和管理过程中的主要问题。对企业的生产管理有着重要和直接的影响，由于资源的稀有和缺失性与企业的生产目标存在着矛盾，通过优化调度对方法用来提高资源的利用率，减少生产成本，对于提高生产管理效益，获得更高对经济有着十分重要的意义。

生产调度问题是一门具有交叉性研究方向，涉及多个学科的理论和应用知识，现在，主要从数学模型的建立和算法的有效设计两个方面研究生产调度问题，前者研究调度问题的数学建模，约束条件和目标函数等问题，后者研究算法的设计，如何有效寻找最优解。

生产调度作为一类最优化问题，可以用如数学线性规划等方法求得最优解。近些年来，随着调度问题的研究越来越复杂，用更短的时间寻求更高质量的最优解成为研究者们关注的重点问题，因此对概率搜索和人工智能的方法有了进一步的探索。