求解调度问题的启发式算法
- 格式:doc
- 大小:265.50 KB
- 文档页数:7
车辆调度优化算法最小化运输成本和时间车辆调度是物流运输领域中一个重要的问题。
在运输过程中,如何合理安排车辆的调度,以降低运输成本和缩短运输时间,是一个挑战性的任务。
为了解决这个问题,人们提出了各种各样的车辆调度优化算法。
本文将介绍一些常见的车辆调度优化算法,探讨它们的优劣势以及在实际应用中的效果。
1. 贪心算法贪心算法是一种常见的启发式算法,在车辆调度问题中得到广泛应用。
它的核心思想是每次选择局部最优解,通过迭代来逐步得到全局最优解。
在车辆调度问题中,贪心算法可以根据某种规则将任务分配给可用的车辆,并选择最短路径进行运输。
这种算法简单高效,但可能会得到次优解。
2. 遗传算法遗传算法是一种模拟自然界进化过程的优化算法。
它通过模拟遗传、交叉和变异等操作来搜索最优解。
在车辆调度问题中,遗传算法可以将车辆路径表示为染色体,通过不断进化来寻找最佳路径。
遗传算法具有全局搜索能力,但也存在收敛速度慢的问题。
3. 禁忌搜索算法禁忌搜索算法是一种基于局部搜索的优化算法。
它通过记录搜索历史并禁忌一些不良移动,以避免陷入局部最优解。
在车辆调度问题中,禁忌搜索算法可以通过禁忌表来记录不良移动,并选择较优的移动策略。
禁忌搜索算法在寻找局部最优解方面表现出色,但可能无法得到全局最优解。
4. 模拟退火算法模拟退火算法是一种模拟固体退火过程的优化算法。
它通过接受较差解的概率来避免陷入局部最优解,并最终逼近全局最优解。
在车辆调度问题中,模拟退火算法可以通过降温和随机移动来搜索最优解。
模拟退火算法具有全局搜索能力和一定的随机性,但需要合理的参数设置。
5. 蚁群算法蚁群算法是一种模拟蚂蚁觅食行为的优化算法。
它通过模拟蚂蚁在路径选择中的信息素沉积和信息素挥发来搜索最优解。
在车辆调度问题中,蚁群算法可以通过模拟蚂蚁选择路径的过程来寻找最佳路径。
蚁群算法具有全局搜索能力和自适应性,但也存在收敛速度慢的问题。
综上所述,车辆调度优化算法有贪心算法、遗传算法、禁忌搜索算法、模拟退火算法和蚁群算法等多种方法。
一种求解Job shop调度问题的启发式组合邻域交换算法崔健双;李铁克
【期刊名称】《管理工程学报》
【年(卷),期】2009(023)003
【摘要】针对job shop调度问题提出一种启发式组合邻域交换算法(HCNA).首先从对任意给定的初始可行调度利用本文提出的最大完工时间贪心算法(CMA)计算出初始可行解,然后利用组合条件邻域交换策略不断地产生新的调度.每当一个新调度形成就调用GMA作可行性判断,过滤掉不可行方案或计算出最大完工时间.对可行方案则反复调用改进的关键路径法(CPA)进行局部优化.文中证明了一个关于调度可行性的定理,指出调度方案的可计算性是其可行性的充要条件.对现有的一些Benchmark问题进行了测试计算,与国内外同类算法最新研究文献中给出的结果作了比较.表明无论从计算时间还是计算精度该算法都占有一定的优势.
【总页数】6页(P97-102)
【作者】崔健双;李铁克
【作者单位】北京科技大学经济管理学院,北京,100083;北京科技大学经济管理学院,北京,100083
【正文语种】中文
【中图分类】TP273.1
【相关文献】
1.一种求解Job Shop调度问题的混合粒子群优化算法 [J], 宋晓宇;张峰;任义;曹阳
2.一种求解Job-Shop调度问题的混合自适应变异粒子群算法 [J], 邓慈云;陈焕文;刘泽文;万杰
3.一种求解Job Shop调度问题的改进遗传算法 [J], 沈镇静;郑湃;李家霁
4.求解Job Shop调度问题的一种新的邻域搜索算法 [J], 曾立平;黄文奇
5.一种求解Job-Shop调度问题的新型蚁群算法 [J], 李胜;周明;许洋
因版权原因,仅展示原文概要,查看原文内容请购买。
求解资源受限项目调度问题算法的研究资源受限项目调度问题是指在一定资源约束条件下,在任务之间存在互相依赖的关系,需要在满足约束条件的前提下,合理的安排任务的执行顺序,以实现最近完工时间或最小化完成时间等目标。
这种问题常常涉及到计算机科学、运筹学、管理科学等领域,并被广泛应用于制造、建筑、航空等领域。
本文将系统介绍资源受限项目调度问题的算法和研究进展。
本文首先阐述资源受限项目调度问题的定义和数学建模,接着系统概述了现有算法中最常用的几种算法,包括启发式算法,遗传算法,禁忌搜索算法以及近似算法等。
最后,本文讨论了问题中所需考虑的特殊约束条件和未来研究的方向。
一、问题定义与数学模型资源受限项目调度问题是对一个由n个任务组成的项目,在一定的资源约束条件下来确定任务完成的调度时间,以最小化整个项目的完成时间。
对于每个任务i,可以定义任务开始时间si和结束时间fi。
我们将任务i的处理时间称为ti,任务i所需要的资源数量称为ri。
对于任务i,我们称任务j有一个前驱任务,也就是必须在任务i开始前完成任务j。
这种依赖称为任务i对任务j的影响,通常被表示为dij,其中dij=0表示仅当任务i开始之前完成任务j时,任务i才能开始。
优化目标是完成时间最小化,也就是最大化满足所有的任务与资源约束条件的时间。
定义完成时间最小化的数学模型为:min fmax=Max{fi}s.t fi≥si+ti ∀i∈{1,2,…n}fi≥fj+dij ∀ i,j∈{1,2,…n} 且dij≠0∑i=1n ri ≤ B其中,fmax是整个项目的完成时间,si是任务i的开始时间,ti是任务i所需的处理时间,dij是任务i对任务j的影响,ri是任务i所需的资源,B是总的资源限制。
二、现有算法研究综述1. 启发式算法启发式算法是最常用的解决资源受限项目调度问题的算法。
启发式算法通常是根据经验或经验规则来指导作出决策。
常见的启发式算法包括贪心策略、模拟退火算法和遗传算法。
柔性作业车间调度问题的一种启发式算法柔性作业车间调度问题是一个复杂的优化问题,其目标是在给定生产任务和作业要求的前提下,最小化车间生产周期,并保证调度结果的合理性。
解决柔性作业车间调度问题的必要方法之一是利用启发式方法,即引入一定的人工规则处理调度问题,采用数据驱动、实例驱动和规则驱动以灵活处理复杂问题,以达到期望的调度结果。
本文将介绍一种启发式算法,其旨在为柔性作业车间调度问题提供一个可行的优化方案。
一、算法介绍本次启发式算法构建基于三个步骤,分别为:(1)任务分配;(2)调度安排;(3)调度优化。
1.任务分配首先,要求对当前车间作业,根据各作业间的关联性把具有相似性的作业归属与相同的任务,并依据作业资源、生产要求等因素,将任务进行拆解分配,具体可采用文丘里极小值算法(Wendong'salgorithm)。
2.调度安排接下来,基于任务分配结果对每一任务中的作业进行调度安排,采用贪心法构建最优调度序列,即将作业一路朝正确的顺序排列,依据单元时间增加进行比较,可以较快速地构建出调度序列,以满足当前复杂制造生产的需求。
3.调度优化最后,要在调度的的基础上,采用基于交换算子的调度优化技术,即针对每一任务、每一任务分配中的作业,对调度情况进行分析,根据时间,贴紧原则,不影响任务完成时间,在一定条件下,找到调度序列中可以进行交换的作业,实现任务最优分配,从而提高整体工厂效率,达到柔性作业车间调度问题的优化目标。
二、算法性能本次启发式算法的性能分析表明,相比其他传统算法,本算法的整体周期时间有了显著缩短,具有良好的计算效率和强大的解决能力;此外,本算法灵活方便,可以有效应对柔性作业车间多变的特点,用于处理带有柔性优先的作业列表,可以构建出更高效的调度方案,从而有效减少车间完成整个任务所需要的总时间。
能源系统中的电力调度算法基于启发式方法的研究电力调度是能源系统中的重要环节,它涉及到电力的生产、传输和消费,对于优化电力系统的运行具有重要意义。
而为了实现电力调度的高效性和准确性,研究者们开始采用启发式方法进行算法设计。
启发式方法是一种基于经验的算法设计方法,通过模仿人类的思考和决策过程来解决问题。
在电力调度中,启发式方法可以通过模拟人类的决策过程来确定最佳的电力调度方案。
启发式方法在电力调度中的应用可以分为两个层面,一是对电力生产和传输的调度,二是对电力消费的调度。
在电力生产和传输方面,启发式方法可以根据当前的电力需求和供给情况,通过模拟人类的决策过程来制定出最优的电力调度方案。
比如,可以通过遗传算法来模拟进化过程,通过逐代优胜劣汰的方式,不断优化电力调度方案。
此外,还可以通过模拟退火算法来模拟金属退火的过程,通过随机搜索和接受较差解的策略,寻找到全局最优解。
在电力消费方面,启发式方法可以通过模拟人类的行为和决策过程来制定出最佳的电力使用方案。
比如,可以通过强化学习算法来模拟人类的学习和反馈过程,通过不断调整电力使用策略,使得电力的利用效率最大化。
此外,还可以通过人工神经网络算法来模拟人类的神经网络,通过训练模型来预测电力需求,并根据预测结果来制定电力调度方案。
然而,启发式方法在电力调度中也存在一些问题和挑战。
首先,启发式方法往往需要大量的计算资源和时间,因此在实际应用中可能面临计算复杂度过高的问题。
其次,启发式方法的算法设计需要基于大量的实验和经验,因此可能存在误差和不确定性。
此外,启发式方法往往缺乏数学上的证明和理论支持,因此可能难以保证算法的准确性和可靠性。
为了克服这些问题,研究者们可以进一步探索和改进启发式方法在电力调度中的应用。
一方面,可以研究和开发更高效和精确的启发式算法,提高电力调度的效率和准确性。
另一方面,可以结合其他优化算法和技术,如深度学习和模糊逻辑等,来改进启发式方法的性能和效果。
考虑柔性维修的job-shop调度问题及启发式算法摘要:机器设备在计划调度期间需要一段固定的时间去从事维修,这种情况在机械制造、IC测试等领域是经常发生的。
文章首先对考虑柔性维修的job-shop调度问题的进行了分析并证明该问题是NP-hard,然后对最优方案的选择进行了证明。
文章提出的调度目标是最小化最大完工时间。
针对本问题的特性,提出了启发式算法并编写程序进行计算实验。
关键词:job-shop调度柔性维修启发式算法在计划调度期间机器设备经常会因为各种原因需要进行维修而出现不能使用的情况,类似问题也经常发生在集成电路测试等领域的作业调度中[1]。
本文的研究目标是寻找考虑柔性维修的job-shop调度问题的最小化最大完工时间,并作出如下假设。
1 考虑柔性维修的job-shop调度方案2 启发式算法及算例针对生产实际中机器维修以及其他多项约束条件的情况,本节提出了最小化最大完工时间的job-shop调度问题的启发式算法,具体如下。
步骤1、步骤2的复杂性分别为O(nlogn)、O(n),故该算法的复杂度是O(nlogn)。
同时我们注意到反复使用本算法也可以解决超过一个维修周期间隔的延长情况。
3 启发式算法的效率评价为了评价上节提出的启发式算法的计算效率,启发式算法程序采用Visual Basic编写,在Pentium4 3.0G个人电脑上运行。
对于下面提出的所有测试问题,本算法的计算时间均少于1秒。
首先根据以下假设条件以随机生成测试用的360个问题,每种类型有30个实验问题。
(1)n等于10,20,30,40,50,60,70,80,90,100,150或200。
(2)是[5,15]区间的均匀分布。
(3)r 是[1,15]或[16,30]的均匀分布。
由于本问题是NP-hard,所以这个计算结果是令人满意的。
4 结论本文的研究目标是寻找考虑柔性维修的job-shop调度问题的最小化最大完工时间。
本文首先对该问题的复杂性进行了分析,并证明该问题是NP-hard,然后对最优方案的选择进行了证明。
一种改进的关键工序算法刘智勇 徐昕江苏科技大学经济管理学院,江苏 镇江 212003摘要:针对max ///n m p F 问题,改进了关键工序法法,该算法同时注重关键工件与关键工序,通过对关键工件与非关键工件在关键工序前后的加工时间计算、比较来获得各工件加工的先后顺序,缩短最长流程时间。
并将该启发式算法与关键工序法进行了对比分析,最后利用仿真的方法来验证所提出的方法的可行性。
关键词:Flow-shop 关键工件 关键工序 启发式算法 最长流程时间 0引言Flow-shop 调度问题(flow shop scheduling problem,FSP )是许多实际流水线生产调度问题的简化模型,它无论是在离散制造工业还是在流程工业中都具有广泛的应用,因此其研究具有重要的理论意义和工程价值。
n/m/p/F max 问题是Flow-shop调度问题中的一种特殊情况,即所有工件在各台机器上的加工顺序都相同,也称流水作业排列排序问题或同顺序排序问题。
其求解方法有精确方法[1](分支定界法、穷举法等)、智能搜索法[2,3,4](神经网络法、遗传算法、蚁群算法等)、启发式算法[4,5,6,7](Palmer 算法、C-D-S 法、关键工序法、最小排序系数法等)等等。
由于Flow-shop 调度问题一般都属于NP 难题(nondeterministic polynomial)。
精确方法只能求解小规模问题,对于大规模问题几乎被认为是无效算法,智能搜索法在求解上虽比启发式算法更接近最有解,但由于设计针对具体问题的智能搜索法对于许多人来说比较困难,特别是对于实际工程人员更是如此。
所以启发式算法仍是用的很多的方法。
主要的启发式算法有Palmer 算法、关键工序法和最小排序系数法等。
其中,关键工序法贯穿着当前先进的管理思想,能够很好的对现实情况进行解释和分析。
然而关键工序法所求的可行解很可能与最优解相差甚远,鉴于此,本文对其进行了改进。
改进迭代贪婪算法求解可重入流水车间调度问题可重入流水车间调度问题(reentrant flow shop scheduling problem)是指在多工序流水车间中,存在可重入现象的调度问题。
在车间中,每个作业需要按照一定的工序顺序加工,而每个工序都有不同的机器可以完成。
不同于一般流水车间问题,可重入流水车间问题允许同一作业在同一工序上重复进行,增加了调度的复杂性和难度。
迭代贪婪算法是一种常用于解决可重入流水车间调度问题的启发式算法。
它的基本思想是通过多次迭代,每次选择当前局部最优的决策来逐步优化最终调度结果。
然而,传统的迭代贪婪算法存在着一些不足之处,例如容易陷入局部最优解、收敛速度较慢等。
因此,本文将针对这些不足之处进行改进,以求更好地解决可重入流水车间调度问题。
一、改进之处在改进迭代贪婪算法求解可重入流水车间调度问题时,我们可以从以下几个方面进行改进:1. 变异操作策略的引入:传统的迭代贪婪算法只考虑选择当前局部最优解进行迭代更新,但这种策略存在着局限性。
我们可以引入变异操作策略,即在每次迭代中,按照一定概率引入一定程度的随机性,以避免陷入局部最优解。
通过引入变异操作,可以增强算法的全局搜索能力,提高算法的质量和效率。
2. 邻域搜索的扩展:邻域搜索是迭代贪婪算法中的关键步骤。
传统的迭代贪婪算法仅仅根据局部最优解进行邻域搜索,但这种策略可能无法充分探索搜索空间。
我们可以考虑扩展邻域搜索的范围,在搜索过程中引入一定程度的随机性,以增加解空间的探索度。
通过扩展邻域搜索的范围,可以更全面地搜索潜在解,提高算法的全局搜索能力。
3. 优化目标函数的定义:目标函数的定义直接关系到算法求解可重入流水车间调度问题的效果。
传统的迭代贪婪算法通常采用简单的目标函数,例如最小化总加工时间或最大化作业的完工时间。
然而,这样的目标函数并不能充分考虑到车间效率与资源利用率等因素。
我们可以重新定义目标函数,结合车间实际情况和约束条件,以综合考虑多个指标,从而求得更合理、更优的调度结果。
一种改进的关键工序算法刘智勇 徐昕江苏科技大学经济管理学院,江苏 镇江 212003摘要:针对max ///n m p F 问题,改进了关键工序法法,该算法同时注重关键工件与关键工序,通过对关键工件与非关键工件在关键工序前后的加工时间计算、比较来获得各工件加工的先后顺序,缩短最长流程时间。
并将该启发式算法与关键工序法进行了对比分析,最后利用仿真的方法来验证所提出的方法的可行性。
关键词:Flow-shop 关键工件 关键工序 启发式算法 最长流程时间 0引言Flow-shop 调度问题(flow shop scheduling problem,FSP )是许多实际流水线生产调度问题的简化模型,它无论是在离散制造工业还是在流程工业中都具有广泛的应用,因此其研究具有重要的理论意义和工程价值。
n/m/p/F max 问题是Flow-shop调度问题中的一种特殊情况,即所有工件在各台机器上的加工顺序都相同,也称流水作业排列排序问题或同顺序排序问题。
其求解方法有精确方法[1](分支定界法、穷举法等)、智能搜索法[2,3,4](神经网络法、遗传算法、蚁群算法等)、启发式算法[4,5,6,7](Palmer 算法、C-D-S 法、关键工序法、最小排序系数法等)等等。
由于Flow-shop 调度问题一般都属于NP 难题(nondeterministic polynomial)。
精确方法只能求解小规模问题,对于大规模问题几乎被认为是无效算法,智能搜索法在求解上虽比启发式算法更接近最有解,但由于设计针对具体问题的智能搜索法对于许多人来说比较困难,特别是对于实际工程人员更是如此。
所以启发式算法仍是用的很多的方法。
主要的启发式算法有Palmer 算法、关键工序法和最小排序系数法等。
其中,关键工序法贯穿着当前先进的管理思想,能够很好的对现实情况进行解释和分析。
然而关键工序法所求的可行解很可能与最优解相差甚远,鉴于此,本文对其进行了改进。
1 max ///n m p F 问题描述max ///n m p F 问题可以描述为:有n 个工件在m 台机器上加工,各工件有完全相同的工艺路线,每一台机器上加工工件的先后顺序也完全相同;一个工件不能同时在不同的机器上加工;每台机器同时只能加工一个工件;各工件在加工完后立即送下一道工序;工件在机器上开始加工,必须一直进行到该工序完工,中途不允许停下来插入其它工件;所有工件在0时刻已准备就绪,机器调整时间包括在加工时间内;允许工件在工序之间等待,允许机器在任务未到达时闲置;优化目标是求出这n 个任务的一个全排列,使其最长流程时间(也称加工周期)max F 最短,则max F 的计算方法如下:,00,,11,1,1,,11,,max,00max(,)(1,2,,1,2,,i j i i i i j i j i j i jn m C C C C t C C C t F C i n j m ---==⎧⎪=+⎪⎨=+⎪⎪==⋅⋅⋅=⋅⋅⋅⎩;其中;) 上式中,i j C 代表工件i 在机器j 上的完工时间,,i j t 代表工件i 在机器j 上的加工时间。
2改进的关键工序法改进的关键工序法要求抓住关键工序和关键工件,定义关键工序为各道工序上加工各个工件总时间最长的工序;定义关键工件为各个工件在各道工序加工总时间最长的工件。
若关键工件都多个,则按照各关键工件首道工序加工时间与尾道工序加工时间的大小分组,首道工序加工时间小于尾道的工件为第一组,首道工序加工时间等于尾道的工件第二组,首道工序加工时间大于尾道的工件为第三组,优先顺序为{第一组,第二组,第三组},对于第一组中的各关键工件之间的排序则按关键工序前各道工序总加工时间从小到大排序,对于第三组的各关键工件之间的排序则按关键工序后各道工序总加工时间从大到小排序,第二组的各关键工件的排序时需先比较第一组与第三组内的工件个数,当第一组的工件个数少于或等于第三组时,第二组内工件按第一组规则排,否则按第三组的规则排。
对关键工件以外的所有工件同样比较首道工序加工时间与尾道工序加工时间,按小于、等于、大于分为三组,其组内排序规则与关键工件个组内排序规则相同。
最后按{非关键工件第一组,非关键工件第二组,关键工件第一组,关键工件第二组,关键工件第三组,非关键共建第三组}的顺序进行总排序,即可获得满意的max F 。
对于关键工序为首道工序的情形,就把次关键工序看成是上述的关键工序,排序步骤不变。
用数学语言表示如下:Step1: 对i ∀,计算,*,1m i i j j t t ==∑,对j ∀,计算*,,1nj i j i t t ==∑,定义{}",*1,*2,*,*|max(,,,)i n i A i t t t t ∈==⋅⋅⋅为关键工件,定义{}"*,*,1*,2*,|max(,,,)j m j B j t t t t ∈==⋅⋅⋅ 为关键工序。
Step2::若()1Card A >(其中()Card 表示括号中集合包含元素的个数),则⑴{}"""1,1,|i i m A i t t =<≠∅,则计算""1,1j i j j t -=∑的值,按该值从小到大排列获得"i 一个排序优先1C 。
⑵{}"""2,1,|i i m A i t t =>≠∅,则计算"",1m i j j j t =+∑的值,按该值从大到小排列获得"i 一个排序优先序列2C 。
⑶{}"""3,1,|i i m A i t t ==≠∅,则①当12()()Card A Card A ≤时,那么按⑴的规则获得3A 中元素的排序;②当12()()Card A Card A >时,那么按⑵的规则获得3A 中元素的排序;设3A 中元素的排序优先序列为3C 。
将Step2:中的各种排序优先序列一起排序,得到1C →3C →2C 。
Step3::若i A ∉,则⑴{}4,1,|i i m A i t t =<≠∅,则计算"1,1j i j j t -=∑的值,按该值从小到大排列获得i 一个排序优先4C 。
⑵{}5,1,|i i m A i t t =>≠∅,则计算",1m i j j j t =+∑的值,按该值从大到小排列获得i 一个排序优先序列5C 。
⑶{}6,1,|i i m A i t t ==≠∅,则①当45()()Card A Card A ≤时,那么按Step3中⑴的规则获得6A 中元素的排序;②当45()()Card A Card A >时,那么按Step3中⑵的规则获得6A 中元素的排序;设6A 中元素的排序优先序列为6C 。
Step4::将上述结果进行总排序优先级:4C →5C →1C →3C →2C →6C 。
经过上述四步,获得的结果就是满意解。
3算法示例设有8个零件A 、B 、C 、D 、E 、F 、G 、H 在8台机器M1、M2、M3、M4、M5、M6、M7、M8上同顺序加工,其工艺过程及工时定额见表1,试求出最长流程时间F max .现利用改进的关键工序法求解:⑴计算每个工件的总加工时间以及每个工序总加工时间,见表,可知关键工件有两个A、B,关键工序有一个M4。
⑵针对A工件,首道工序加工时间大于尾道工序加工时间,B工件,首道工序加工时间小于尾道工序加工时间,自然A排B的前面,即A→B。
⑶对剩余工件,按首道工序加工时间大于、等于、小于尾道工序加工时间分成三类,可得首道工序加工时间大于尾道工序加工时间的工件有C、D、F;首道工序加工时间等于尾道工序加工时间的工件E;首道工序加工时间小于尾道工序加工时间的工件有G、H。
①对C、D、E、F按关键工序前的各道工序时间相加(M1+M2+M3),得到T C=6+2+10=18,T D=9+4+9=22,T F=2+5+0=4,则C、D、F的排序按T值从小到大为F→C→D;②对G、H按按关键工序后的各道工序时间相加(M5+M6+M7),得到T G=5+3+2+6=16,T H=5+2+3+4=14,则G、H的排序按T值从大到小为G→H。
⑷按{首道工序加工时间大于尾道工序加工时间的工件,首道工序加工时间等于尾道工序加工时间的工件,关键工件,首道工序加工时间小于尾道工序加工时间的工件}的顺序进行全排,获得F→C→D→E→A→B→G→H。
4算法测试与比较通过MATLAB 程序对max ///n m p F 问题进行100次仿真,将关键工序法和文中提出的改进方法进行了对比。
结果如图1所示:图1 不同规模Flow-shop 求解结果比较a) m=50,n=50b)m=100,n=100c)m=150,n=150d)m=200, n=200可见,本文所提出的改进方法普遍优于原本的关键工序方法。
当所要求解的Flow-shop问题规模较小时,如图1中 a)所示,改进方法不略于关键工序法。
但两条曲线几乎重合,优势比较小。
这说明在规模较小的Flow-shop问题中,关键工序法依然十分有效。
然而,当问题规模较大时,如图1中b)所示,本文中的改进方法明显优于关键工序法。
这说明关键工序法在大规模问题中,相对于最优解将产生明显偏差,并且这种偏差是随着问题规模的扩大而增大的。
而本文所提出的改进算法,恰恰弥补了关键工序法在大规模Flow-shop问题中表现较差这一问题。
5参考文献[1] Liu Lili Tang Guochun. A Branch and Bound Approach and Heuristic Algorithms for Scheduling a Batching Machine[J].2004,8(3):39-44.[2]REEVES C R. A genetic algorithm for flowshop sequencing[J].Computer and Operations Research,1995,22(1):5-23.[3]RAJENDRAN C,ZIEGLER H. Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime jobs[J]. European Journal of Operational Research,2004,155(2):426-438[4]叶春明生产计划与控制[M],北京:高等教育出版社,2005:391-400。