英语原文共 25 页，剩余内容已隐藏，支付完成后下载完整资料
具有抢占、机器空闲时间和不相等释放时间的准时制单机调度的混合粒子群优化算法
摘要：论文研究准时生产中允许抢占的，投产时间不相等的，允许非强制机器空闲时间的单机调度问题，这些假设来源于制造环境中的现实问题，研究目的是最小化总加权提早及延迟成本。延迟是在生产系统中需要关注的一个至关重要的问题，用以解决销售缺货（backorder）和订单损失。因此，我们采用了JIT的概念，其它考虑元素包括允许机器抢占，允许（非强制）机器空闲时间，以及不均等的投产时间。我们提出一个新的数学模型，并且由于该问题的NP-hard特性，我们提出了三种元启发式算法：混合粒子群算法（HPSO），遗传算法和帝国竞争算法。在混合粒子群算法中，以一定的概率采用了基于云理论的模拟退火法来避免陷入局部最优。田口方法被用于校准提出的算法参数。给出了若干计算实例的求解来证明我们所提出方法的有效性。我们依据相对百分偏差和计算时间对本文提出的算法进行评估，计算结果表明HPSO算法的计算结果相比其他算法质量更好。
关键字：单机 准时制调度 抢占 机器空闲时间 释放时间 云理论 粒子群优化 基因算法 帝国竞争算法
- 引言
准时制（JIT）调度问题属于多准则调度问题的一部分，调度领域的研究人员对这些模型给予了高度关注，因为这些调度所涉及的领域在工业高层管理之中具有现实意义。事实上，JIT旨在识别并消除浪费，譬如过度生产，等待时间，运输时间，移动时间，库存和瑕疵品。 在JIT环境中，比截止时间提早完成的工作可能会造成一些机会成本，产品毁坏和库存持有成本。同样，延迟也可能造成损失顾客、合同违约金、销售损失以及名誉损失。很清楚的是，一个理想的调度模型应当是所有的工序都在到期日恰好完成，因此包括提早和延迟成本都在内的标准由于他们的现实意义和相关性能够在过去的几十年中得到较大的关注。回想一下，如果一个作业可以在任何时刻被中断，并且不用任何花费就能完成，我们就称这样的情况为允许抢占。 生产车间内允许抢占的情况产生可以有若干原因，例如一个工作的执行可以被暂停，进行冷却或干燥，接下来可以在相同或者不同机器上继续加工。在所有制造环境模式中，机器准备成本是生产调度的一个重要因素。在现实调度配置中用得最为广泛的假设之一是与顺序相关的机器准备成本，比如机器清洗或者更换工具。由于JIT调度在工业应用中可以解决影响顾客满意的需求满足的不确定性，因此本研究提出了一个全面的模型，详细阐述了调度问题的若干个方面：一方面，抢占、投产时间不相等、非强制机器空暇时间；另一方面，JIT调度。所有这些特点形成了一个对现在竞争型产业有重要意义的一个模型。最近，工厂都配备有自动化无人驾驶机以及精密生产所需要的工具。并且，市场和顾客通过准时送达来对产业部门进行评估。文献分别研究了JIT调度涉及的以上各个方面，但这对现今的工业并不那么有效。因此，我们提出的问题旨在清楚研究出一个JIT调度模型，这个模型建立在单机调度下，并考虑了抢占、投产时间不相等、非强制机器空闲时间，而这些在大量现实的工业应用中都是真实发生的。由于很难用精确的算法来解决这个问题，我们为了真实可靠，设计了一个混合启发式方法。在这个解决方法中，我们也做了一些创新以获得具有更高质量和更短获得时间的结果。与此同时，一些用相关表格呈现出来的计算结果也用于呈现这个模型的分析要点。
本研究的余下篇幅组织如下：第二节为文献综述，第三节描述这个问题和相关假设，提出的粒子群算法，遗传算法以及帝国竞争算法（ICA）在第四节。第五节讲述田口方法作为提出来的算法参数工具，第六节为计算结果。最后第七节给出结论和未来研究方向。
- 文献综述
在近几十年，JIT调度问题在产业系统变得重要起来。延迟和提早调度问题，即所谓的提早/延迟问题，首先是由Sidney（1977）提出来的。迄今为止，许多报纸已经对有提早和延迟成本的单机调度模型做了研究。Valente 和 Alves等（2005a）对在JIT环境中不具有机器空闲时间的单机调度问题提出了一种派工法则和贪婪程序；他们改善了由他们的启发式算法得到的结果。Valente等（2005b）使得有投产时间不相等，但是并不允许有非强制机器闲工时间单机调度问题得到解决。Hoogeveen（2005）重新审查JIT调度问题，并集中审查多准则调度。Valente 和Moreira（2009）考虑了没有机器闲工时间和二次提早延迟成本的单机调度问题，并提出和比较几种派遣启发方法。Valente（2008）提出了一个针对JIT环境的单机调度问题启发式搜索法，该环境具有依赖于作业的罚金，并不具有机器闲工时间。
Hendel，Runge，和Sourd（2009）介绍了非抢占的相关模型。Gurel和Selim Akturk（2008）尝试同时考虑工艺规划、调度和预防性维护决策。这个目标是使数控机床上的总完成时间最小。他们依照在数控机床上可控制的处理时间为依据做决定，提出一种新的启发式搜索算法，这个算法可以同时决定作业处理时间，作业顺序以及预防性维护调度。Alvarez-Valdes 等（2010）提出二次整数规划模型，解决了总加权提早和延迟费用最小目标的问题。Motaghedi-Larijani等（2011）考虑了一个有序列相关准备时间的单机调度问题，目的在于依据机器智能恶化处理和修复时间来使得所有作业的总提早和延时成本最小。维护作业旨在减少作业的处理时间。他们运用一种新的混合粒子群模拟退火法来获得一个合理运行时间的最优结果。计算结果表明粒子群算相比其他研究过的算法有更好的表现。Khorshidian等研究了在JIT环境中并具有抢占的单机调度问题，提出用遗传算法来解决问题。Huang（2012）考虑了一种缩短作业处理时间的单机调度问题。问题的目标是找到一个能最小化绝对最大延迟时间的计划表。他们表明这个问题可以用多项式时间来解决。Benmansour，Allaoui和Abdelhakim（2012）研究了最小化基于随机共同截止日期的总加权完成时间期望偏差值的单机调度问题。作业的处理时间服从指数分布，共同截止日期服从爱尔朗分布，他们阐明最优调度还需要调整。Jula和Rafiey（2012）在有序列相关准备时间的单机上研究了几个作业的选择和调度，并严格地在每一个作业的开始时间上设置了时间窗。他们阐述了一种基于网络的算法来维持在制造环境中作业的正常进行。提出算法的有效性和鲁棒性可以运用穷举搜索法来进行分析和比较。Mahnam，Moselhi和Fatemi Ghomi（2013）对具有不相等投产时间和空闲时间点的单机调度问题做了研究，以最小化最大提早和延迟时间；他们提出两种名为遗传算法的派遣规则，粒子群优化算法也被提出来解决这个问题。Kayvanfar等（2013）研究了具有可控处理时间的单机调度模型来最小化总延迟和提早时间。他们提出对小问题运用三种元启发式方法，对中等规模或者大规模问题运用二种元启发式方法来作为有效局部搜索法。Birgin和Ronconi（2012）解决了一个具有共同截止日和每项作业有非完全准备时间的单机调度问题，问题的目标是最小化作业提早和延迟罚金的总加权成本。由于该问题具有所谓的非确定性，为了改善结果的质量，开发该问题的某种特性的建设性启发式算法的应用被研究出来。Yin等（2012）考虑了一个具有可分配的共同截止日期和可控时间的单机运输调度问题。这个问题的目标是使基于加权提早和延迟作业数，工作持有，到期日分配，分批交付，完工时间和资源消耗最小化。Jula和Kones（2013）解决了在有序列相关准备时间的单机上几个作业的选择和调度问题，并严格地在每一个作业的开始时间上设置了时间窗。他们介绍了一种基于析取约束的两步数学规划模型来解决这个问题。这些方法的目的是最大限度地减少作业的总定义得分，同时满足每个班次作业大类的生产目标。他们的模型是要最小化所有已选择作业的最大完成时间；有效性、效率以及所提出的算法的鲁棒性在文献中都有分析。
现在，我们简短地回顾一下粒子群算法、遗传算法和帝国竞争算法最近在调度问题中的用法。Victor Raj，Saravana Sankar，和 Ponnambalm（2011）为了使得集装效率最大化从而使得生产系统效率最大，他们通过应用多特征集装环境的批量选择集装方法提出一种粒子群算法。他们通过一组实验问题数据集对该算法进行了测试，发现其优于传统的选择性装配和顺序装配方法，因此具有较高的制造系统效率。Wang，Zhang和Fuh（2012）考虑了用一种可以确定一系列操作方法（机器和设置配置）的工艺规划，这些操作方法可以将给定的库存转化为设计的零件。他们应用粒子群算法来解决提出的问题，并且将两种局部搜索法和粒子群算法结合在一起。计算实例表明了粒子群算法能够获得一个良好的结果。Lei和Guo（2012）针对模糊柔性作业车间调度问题提出了一种基于群的高效领域搜索算法；他们阐明基于群的高效领域搜索算法比现存文献中描述的方法都要好。Lian等（2012）运用帝国竞争算法将工艺规划与调度问题相结合以求得最小化完工时间。他们提出了基于操作并包括各种工艺规划灵活性的表示方案。帝国竞争算法的计算结果与IPPS现存的一些算法相比较，证明了所提出的帝国竞争算法的高效性和有效性。Vannazyar和Salmasi（2012）考虑了序列相关准备时间的流水车间调度问题以使得延误作业数最小。他们研发了一种混合整数规划模型并应用多种元启发式算法，主要是TS算法和ICA算法来解决这个问题。 他们利用基于裂区实验法的统计实验来获得最佳的算法。实验的结果表明ICA（帝国竞争法）和TS（禁忌搜索算法）的混合所得到的结果质量要优于其他算法。Seidgar等（2014）考虑两阶段流水车间问题来最小化总加权完工时间和平均完成时间。他们通过帝国竞争法与神经网络相结合来解决该问题，并将其与Torabzadeh和Zandieh提出的基于云理论的模拟退火法相比较。计算结果表明所提出的算法具有更高的质量。Mejia等（2012）提出遗传算法和Petrinets方法相结合，这就将Petrinets方法的建模能力与遗传算法在制造系统调度上的优化能力相结合。Chiou，Chen，和Wu（2013）研究双流水车间调度问题。调度目标是使得松弛时间的变化系数最小，松弛时间表示的是到期日和一项作业的总完成时间的差别。他们提出了五项基于遗传算法的解决方法来解决这个调度问题，这五个方法分别被称为GA-EDD，GA-FIFO，GA-SPT，GA-LFO，和GA-COMBO。数值实验表明GA-COMBO要优于其他四种方法。Han等（2014）提出了一种新的基于遗传算法的无死锁调度方法和柔性制造系统的Petri网模型。优化标准是使得完工时间最小。他们分别在染色体上的两个部分进行不同的交叉和变异操作以改善算法性能。计算结果表明提出的算法可以获得更好的调度方案。在这里，我们只是简单地研究了PSO、GA和ICA，如果为了更好地理解他们，请读者翻阅以前的报告比如：（Tseng et al. 2010; Jolai et al. 2012; Rabiee, Zandieh, and Jafarian 2012; Azadeh et al. 2013; Chen et al. 2013; Ngoc et al. 2014; Xiong and Xing 2014).
正如表格1中显示的，我们都知道，考虑抢占、投产时间不相等和非强制机器空闲时间的JIT单机调度问题在之前的研究中都没有涉及，而这些都是在许多现实工业应用中都会涉及的。
- 问题定义
一系列n个独立作业（j1; j2; . . .; jn）需要在一个机器上加工，在一台机器上每一个作业都有一个投产时间、一个截止日期和一个处理时间。不失一般性，我们假设这些参数都是正的。目标是找到一个使得总加权提早和延迟作业数和序列相关准备时间成本最小的抢占调度。由于不是所有的作业都在调度范围内，但作业之间的抢占能够增加他们的准备成本，所以抢占作业增加总加权提早和延迟作业数是有可能的。因此，我们要在调度范围内调度作业来在两个目标之间寻求一个平衡。这个问题发生在大量的制造业，因为往往瓶颈发生在沿装配或者生产线的单机上。因此，在瓶颈上恰当的序列和调度作业对企业的规划有帮助。单机调度环境确实有许多实际应用。也是，对决定许多制造系统的绩效来说，通常情况下，单机调度的质量是要被考虑在内的。此外，这些问题的结果和见解经常可以用于更复杂的调度环境，如流水作业，加工车间和制造单元的构建。
在这个问题中，一些假设如下：
1）作业的处理时间和截止日是确定的。
2）一个作业可以因在转移到相同机器上冷却或者干燥而被暂停（作业的抢占是被允许的）。
3）每一个作业都有一个释放时间（作业可以在范围内到达）。
4）考虑序列相关准备成本，忽略准备成本。
5）在作业之中没有优先约束。
6）机器从零时刻开始就是持续可工作的，不存在故障。
7）每台机器最多能同时处理一个工作。
下标
i,j作业指数i,=1,hellip;,n
k,l,s,g 周期指数k = 1,2,hellip;,H
参数
n 作业数目
m机器数目
H调度长度（调度范围）
Pi 作业i的处理时间
Ri 作业i的释放时间
di 作业i的截止日
ai 每单位时间作业i的提早成本
bi 每单位时间作业i的提早成本
Costij 作业i处理完后作业j的准备成本
决策变量
Xik 1第i项作业指派时间为k
0 其他
Wikjl 1 如果在k时刻作业i处
全文共6126字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[144250]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
