摘 要

针对车间调度问题(Job-Shop Schedualing Problem)在当下缺少有效解决方法的现状，本文建立了多目标柔性调度车间的模型，引入了K-Means聚类技术的概念方法，提出了使用改进模拟退火算法解决该问题的思想，在使用模拟退火算法寻找最优解前，首先用K-Means聚类技术关于闵可夫斯基距离对潜在解的范围作出聚簇，改进了模拟退火算法的效率，一定程度上克服了模拟退火算法由于对初始温度和降温速度导致的优化时间较长的缺点。之后再使用基于概率的三种邻域搜索方法求取新解，用模拟退火算法对其处理得到优化结果。最后结合了某铸造车间的实际生产数据进行运算，通过五个实际案例验证了算法的有效性和可靠性。

关键词：车间调度问题;K-Means聚类;模拟退火算法;邻域搜索算法;柔性车间调度问题

Abstact

In view of the current situation of Job-Shop Schedualing Problem lacking effective solutions, this paper establishes a multi-objective flexible scheduling workshop model, introduces the conceptual method of K-Means clustering technology, and proposes the use of improved simulated annealing algorithm. To solve this problem, before using the simulated annealing algorithm to find the optimal solution, firstly use K-Means clustering technique to cluster the range of potential solutions for the Minkowski distance, and improve the efficiency of the simulated annealing algorithm to some extent. The shortcomings of the simulated annealing algorithm due to the long optimization time caused by the initial temperature and the cooling rate are overcome. Then, using the three neighborhood search methods based on probability, the new solution is obtained, and the simulated annealing algorithm is used to process the optimization results. Finally, the actual production data of a molding factory is combined to calculate the effectiveness and reliability of the algorithm through five practical cases.

Key words：Shop Scheduling Problem，K-Means Clustering，Simulated Annealing Algorithm，Neighborhood Search Algorithm, Flexible workshop scheduling problem

目录

目录 1

第1章 绪论 1

1.1引言 1

1.2研究背景和意义 1

1.2.1研究背景 1

1.2.2研究意义 2

1.3国内外研究现状 2

1.3.1车间调度研究现状 2

1.3.2模拟退火算法研究现状 3

1.4本文的研究内容和组织结构 3

第2章 车间调度理论 5

2.1车间调度的概述 5

2.1.1车间调度的特点 5

2.1.2车间调度方案的评价 6

2.2柔性调度车间 6

2.2.1柔性调度车间的描述 6

2.2.2柔性调度车间的限制条件 6

2.3研究方法 7

2.3.1精确方法 7

2.3.2近似方法 7

第3章 考虑生产成本的多目标车间调度模型 10

3.1问题描述 10

3.2模型构建 10

3.2.1基本假设条件 10

3.2.2符号含义 11

3.2.4目标和限制 12

第4章 基于K-Means聚类的改进模拟退火算法 14

4.1模拟退火算法 14

4.1.1传统算法的局限性 14

4.1.2模拟退火算法的概述 14

4.1.2模拟退火算法的参数设定 14

4.2 K-Means聚类技术 15

4.2.1聚类技术概述 15

4.2.2 K-Means聚类技术 15

4.2.3 K-Means聚类的优点和不足 16

4.3混合算法 17

4.3.1编码和解码 17

4.3.2邻域搜索 18

4.3.2算法步骤 18

4.3.3算法流程图 19

4.3.4算法评价 20

第5章 算法案例 21

5.1案例描述 21

5.2原始数据 21

5.3计算结果 23

结论 26

参考文献 27

致谢 29

第1章 绪论

1.1引言

在中国制造2025三步走的战略正式启动和世界范围内新一轮产业洗牌和技术改革的影响在我国逐渐产生影响的大背景下，全新的历史性的机遇和挑战摆在了我们的面前。对决策者而言，制造是无法绕过去的一项重要工作，没有强大的制造业就谈不上发展其他产业;对于生产制造企业而言，改进生产管理技术以适应这些新的要求已经成为了新时代制造业竞争的核心。其中车间调度问题的优化已经成为了一个解决该核心问题的潜在突破点。车间调度问题起源于上世纪五十年代Johnson等一批专家结合运筹学和数理统计的方法对双机床车间的优化研究，之后范围不断拓展，基本可以描述为：有一定数量限制的生产机床和生产任务，管理人员需要在满足自然处理顺序的同时找出更优秀的流程或生产安排方案^[1]。在这个过程中忽视了实际可能存在的诸多问题，如机床可能出现故障，订单可能发生变化，原材料的供应可能出现阻碍等。同时现代的订货商也有更加多变的需求如个性化定制、小批量多品种定制等。这两者使得原本就是NP-Hard(Non-deterministic Polynomial Hard)问题而难以用通用方法求出最优解的车间调度问题更加棘手。考虑到大规模生产企业对于此类优化更有需求，排除掉难以适应该情况的数学计算法，而使用机床学习的方法，发挥其自我学习，有效解决非逻辑性建模的优势，是一种潜在的突破口。

1.2研究背景和意义

1.2.1研究背景

对车间调度问题的研究已经经过了数十年的发展，各国学者相继提出了多种算法和车间调度问题的结合思路，取得了一定的成绩。然而当前整个NP-hard问题都缺少有效的解决手法，作为其中最具有知名度的难题之一的车间调度问题，其柔性生产的需求和并行生产的特殊性又使其比传统NP-hard问题解决起来加倍困难。同时，自从我国加入世界贸易组织已经过了接近二十年，我国生产工作中与发达国家的差距仍然明显，尤其是调度方面，许多生产企业还处在粗放式的、随机应变的调度状态，一定程度上浪费了生产效率，增加了生产中的等待时间。基于这种情况，JSP问题的热度正在不断提高，走入到了各国学者的视野中。由于当前国际先进的生产企业都已开始走向智能化、灵敏化，JIT(Just-In-Time)也成为一种新的要求;我国也提出了建设现代化的工业体系，向德国等先进制造业大国借鉴经验。为了满足这些需求，单一算法的局限性渐渐成为一种阻碍，使用多种算法相结合，共同优化已经成为了对车间问题研究的主流方向。模拟退火算法技术近年来备受重视，其有概率跳出局部最优解的特点使其成为优化车间调度问题的常用工具。不过其依赖参数设置，要求初始温度的缺陷阻碍其进一步发挥作用。国内外学者设计了多种算法与之结合，但依然存在进一步优化的可能。

1.2.2研究意义

这项研究同时对生产企业、学术和国家相关行业的发展有一定的意义。此研究缩短了生产企业处理过程的等待时间，使其生产过程更加平滑;通过对生产调度模型的优化，生产成本水平大大降低，同一时间内可以生产更多的产品。现场调度人员也可以减轻对于经验和直觉的依赖，将这项工作从经验性的工作转移到技术层面上。促进各项算法的发展，启发广大研究者将更多算法和理念应用到生产领域。总体而言有利于国家制造业的进步，有利于逐步缩小和制造业先进国家之间的差距。

1.3国内外研究现状

1.3.1车间调度研究现状

虽然在几十年的发展中有许多新的突破和改进并发展出了多个体系，但目前车间调度问题本质上还是经典调度理论的延续。1954年被认为是整个车间调度理论发展的元年，由于这一年Johnson提出了著名的规则法：johnson规则，为研究将来的各项优化方法开拓了思路。之后Simth等人结合了系统性和复杂性的研究完善了该体系。二十一世纪前后，随着计算机技术的发展，人工神经网络、系统建模与仿真、遗传算法等智能算法也被用于该问题之中，目前依然是优化车间调度问题的热门方案。自本世纪开始，车间调度问题已经获得了较高的关注度。

在国内，姚远远等将灰狼模拟算法用于车间调度研究，与布谷鸟算法比较后改进了变异操作，并证明其鲁棒性的提高^[2]。曹睿、侯向盼等在《基于改进遗传算法的柔性车间调度问题的研究》中提出一种求解该问题的改进遗传算法，结合具体情况改进了参数，提高了效率^[3] 。喻明让，陈云等基于Pareto档案提出了改进粒子群优化算法解决车间调度问题，在其中加入了遗传算法的变异思想^[4] 。任彩乐，张超勇首次将候鸟优化算法引入到车间调度问题中，设计了四种邻域结构和双层编码方式求解^[5] 。覃远年，梁仲华讨论了蚁群算法的参数设置以及在车间调度问题中的具体应用^[6]。汤可宗，丰建文探讨了用多策略粒子群算法求解流水线车间调度问题的思路，加快了求解速度^[7]。王凌，王晶晶从绿色制造的角度，研究了如何通过资源调配和操作控制实现环境和生产的双赢^[8]。

国外近年来研究有：Zhao Boxuan等在研究多目标调度问题时，把问题划分为两个子问题，用两代帕累托蚁群算法计算最优解^[9]。Elahe Shokouhi将过程计划和调度决策整合在一起，建立了数学模型优化车间调度问题，缩短了交付周期^[10]。Abdolrazzagh-Nezhad M，Nababan.E.B等提出了一种避免对技术要求过高的初始种群建立方法，证明了在确定生产数量和流程后使用跳过策略(Skip Strategy，SS)也能取得最优解^[11] 。

1.3.2模拟退火算法研究现状

模拟退火算法的研究常年与其他各种理论同步进行，互通有无。由于其具有跳出局部最优解的优点，但是在大规模问题的求解上有困难，研究者往往把它和其他算法相结合。Ye, Zeyang等将并行计算和模拟退火算法想结合，提出了一种新的本地搜索算法，避免了传统方法的离线预处理的高成本，把MSR(mobile sequential recommendation)问题的计算周期从几天缩短到几秒^[12] 。Xiao Liu等用结合模拟退火算法规划无人驾驶飞行器的路线，提出了无人机数据采集方案(optimal UAV data collection trajectory ，OUDCT) ^[13] 。Bouhmala Noureddine把Kernighan和Lin算法(Kernighan and Lin algorithm，KL)与模拟退火算法结合，引入到最大可满足问题中，通过标准算例验证了有效性^[14]。刘焕淋、朱平鑫等提出了一种改进的遗传模拟退火算法，使用这种算法对可见光通信系统中寻找LED调节参数的过程进行优化，提高了该运算的效率^[15]。王雷震、朱锦文等针对信息技术外包工作中里遇到的两层优化问题，把模拟退火算法和自适应机制引入遗传算法中，形成了混合算法，提高了传统遗传算法的局部搜索能力^[16]。何东东针对柔性作业车间调度问题中求解效率低下的问题，将传统遗传模拟退火算法加以改进，使用了非齐次的降温策略和新的自适应遗传因子，提高了该算法温度控制能力^[17]。何庆、吴意乐针对旅行商问题求解困难、传统模拟退火算法收敛速度慢的问题，提出了一种改进遗传模拟退火算法，基于每个个体的适应度提出一种Metropolis准则,改善了模拟退火算法的效率^[18]。陶重犇，雷祝兵等在研究搬运机床人路径规划的过程中把模拟退火算法和栅格法相结合，解决了传统贪心算法的局部收敛问题^[19]。佘智勇，庄健敏将模拟退火算法运用到改进的旅行商问题模型中，降低了配送成本和时间。^[20]

1.4本文的研究内容和组织结构

此研究一开始先初步讨论了车间调度的概念，以及模拟退火算法（simulated algorithm）的基本原理。还介绍了K均值聚类算法的基本条件和注意事项。然后围绕着车间调度中有什么限制因素，有什么判断一个调度是否优秀的判据，在一定假设的前提下建立了最基础的模型，之后用模拟退火算法、遗传算法和K-Means求取优化解。构建算法后，将其应用在具体案例中，验证了其有效性，最后得出总结。本文的路线结构图如图1.1，值出了每一章之间的连接和递进关系。

第一章：站在世界经济政治大背景的角度，分析了当前国内外大形势带来的对车间调度问题研究的新的要求与当前缺少能有效解决车间调度问题手段的现实困境，阐明了研究该问题的必要性所在。汇总了了最近几年国内外学者对FJIP和SA的研究经验与方向，并梳理了全文结构组织。

第二章：首先概览了车间调度问题的发展历程和基本模式，研究了此问题的特殊之处和困难之处。探讨了FJSP及其通用的假设条件与限制因素。总结介绍了了包括精确方法与近似方法在内的多种研究技术。

第三章：提出了考虑生产成本的多目标车间调度问题，确定了基本假设条件和用到的参数符号，建立了基于生产成本和生产时间双目标的、多限制的数学模型。

第四章：介绍了模拟退火算法和K-Means聚类技术的基本概念，指出了两者现有研究中发现的不足与优点，提出混合模拟退火算法和K-Means聚类技术的混合算法，引入邻域搜索和闵可夫斯基距离的概念，设计算法步骤并画出算法流程图，还对其进行了初步评价。

第五章：介绍了某铸造车间的生产条件，收集了流程和成本的基本信息，应用了第四章提到的模型求出了优化结果，以甘特图和表格的形式证明了该算法的有效性。

总结：对全文的工作进行梳理，分析了现有算法的效果，指明了当前研究的进步和不足之处，为进一步深入做了准备。

图1.1 本文结构路线图

第2章 车间调度理论

2.1车间调度的概述

车间调度问题的研究离不开其从属的问题大类。生产调度问题和项目调度问题并称为两大调度问题，在各自的领域已经发展了数十年。其中生产调度起源于对工厂等处理场地调度计划的研究，按照具体的领域，可以划分为单车间调度、线性车间调度、自由车间调度等。生产调度问题常被描述为在某项生产中，总的生产资源和时间限制是确定的，管理人员需要使用多种优化方法对具体分解的各项生产任务之间的顺序流程进行安排，在这个过程中不能违反生产本身的限制。藉由这些计划来接近对生产周期和生产消耗的更优化。

车间调度问题(Job-Shop scheduling Problem，JSP)是调度问题中最经典最基础的一个，它把调度中许多复杂的情况忽略和简化，提炼为这一模型。尽管如此，本质上车间调度问题依然是一个NP-hard问题，没有最优解的精确算法。

JSP可以这样描述：在受限制的期限内，有m台处理机床和n个产品。产品的处理必须满足一定的流程限制条件，每个流程的处理时间是固定的，每个流程记作流程，在此基础上达到处理时间的最短和成本的最低。

车间调度问题的目标在于实现处理时间的最少和生产成本的最低等需求的尽量优化。限制条件包括处理流程的限制、一台机床同时只能处理一个产品、每个产品同时只能处理在一台机床上等。除此之外，在特定的案例中还会加入一些特殊的限制条件，如机床不能连续不断地运转等。

2.1.1车间调度的特点

车间调度问题具有许多特点，包括限制条件多、随机事件多、内部复杂、离散性强等。正是这些特点使得求解车间调度问题十分困难，研究者需要同时考虑多方面的情况。

限制条件多。在车间调度中限制条件包括全局限制、工艺限制、流程限制和资源限制。首先处理时一台机床同时能处理的产品数都不同，然后每个产品不同流程处理需要的工艺都不同，对机床的要求也不同。每个产品都有自己的流程顺序要求，不同的产品的流程之间有时会发生冲突，导致机床不得不闲置一段时间。除此之外，材料，机床，人员等也限制着车间调度问题的解决。

随机事件多。虽然理想情况下的车间调度问题需要考虑的知识正常生产工作本身，但是在实际处理中，各类随机事件的影响是不可忽视的。如机床机床故障、材料供应暂时阻断、处理人员因故不能正常工作、订单突然修改或取消等。这些因素的出现几乎完全没有预兆，会一定程度上影响生产，使得缺乏柔性的生产企业产生损失。

内部情况比较复杂。车间调度问题是包括处理机床、处理人员、处理原料、处理场地、储存、物流等一系列问题的组合。这些因素之间互相影响，互相制约，单纯的对其中某部分求最优意义并不大。同时就处理机床处理产品而言，由于各种等式和不等式限制条件多，而且会受到各种随机事件的干扰，这使得本就是NP-hard问题的车间调度问题更加复杂，使用精确法求解收效不理想。

较高的灵活性。高度的复杂运算同时也给灵活性提供了可能。由于该问题没有精确快速的解法，学者们提出了众多启发式算法对其求解，并互相吸收不断改进，使得解的优秀程度不断提高;另外当前柔性作业车间已成为主流，对于生产数量不确定的情况也可以应对，这对于调度人员而言既是机会又是挑战。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：