单台计算机预测调度使用插入空闲时间

文摘

一台机器被认为是预测调度问题。主要的目标是最小化总完工时间。日程安排的可预测性是衡量完成时间预测计划,实现计划之间的偏差。选择代理的可预测性评估完成时间偏差。优化的两个主要目标和可预测性。为了吸收中断的影响,预测计划是由插入空闲时间。右移位重排方法作为延期策略。三种方法旨在构建预测时间表。计算实验表明,这些算法提供高可预测性与小牺牲在商店的性能。

1。介绍

生产调度是一个决策过程,有关资源分配为优化一个或多个机器上的任务调度目标(1,2]。它扮演着一个重要的角色在大多数生产和服务系统3- - - - - -5]。在传统的调度问题,将不考虑不确定性(1,6]。但是,在现实情况下,中断天生存在的制造环境。这样的中断的例子包括机器故障,新工作移民,移民工作,工作取消,处理时间变化,到期日期变化,不可用的原材料或工具。处理这些中断在生产环境中是一个非常重要的因素的调度算法的设计。

麦凯et al。7)分类为三个主要类别的不确定性在实际生产环境:(i)完整的未知数,(2)怀疑未来,(3)不确定性。完整的未知数是那些没有预先的信息是可用的。他们是不可预测的。对未来的怀疑来自经理的经验和直觉。两种类型的不确定性都是很难纳入生产计划。已知不确定性意味着一些信息可以预测进度时生成的。例如,机器故障属于已知的不确定性,以及他们的发生和持续时间可以用概率分布来描述。大量的理论研究和实践表明,有大量的参数指数分布在工业生产和设备的可靠性分析。在本文中,我们处理相同的假设之间的时间间隔连续两个机器故障是指数分布在4,8- - - - - -10]。

正如我们所知,机器故障是常见的在制造系统中断。为了吸收机故障中断的影响,预测的时间表提前生成插入空闲时间在实际生产系统(11- - - - - -13]。调度过程如下。最初的时间表(称为预测时间表)根据机器生成环境和当前订单的信息。然后预测的时间表执行。当机器发生故障时,预测时间表修改,以提高性能和减少中断的影响。顶尖的时间表(称为实现进度)后获得的所有工作已经处理。生成预测计划在不影响计划活动,预测计划,实现计划之间的差异应该控制,同时保持高店性能。

我们简要讨论一些工作相关的预测调度问题。梅塔和Uzsoy9)提出了一个预测调度方法插入空闲时间安排。在加工车间调度问题是最小化最大迟到环境随机机器故障。结果表明,预测调度提高了可预测性大大小小的牺牲的性能。马路et al。10)被认为是预测调度问题的一台机器与机器随机故障最小化总迟到。类似于(9,10),梅塔和Uzsoy4]构造预测调度单台机器的最小化最大迟到与释放时间和机器故障。刘等人。8)认为是单一的预测调度机器与机器故障最小化加权总迟到。他们提供了一个两级multipopulation遗传算法。事实上,空闲时间的插入方法预测调度一般两阶段算法。一个初始序列决定不考虑机器故障在第一阶段。预测计划是由插入一些空闲时间在第二阶段。在本文中,我们以总完工时间为目标。我们构建预测计划通过使用类似的算法(4,9,10),但引入的新方案考虑反馈空闲时间的影响。

本文的其余部分组织如下。节2,我们提出的问题制定单独的机器调度问题最小化总完工时间。节3,我们提供了一些问题的预赛。我们选择代理的可预测性评估完成时间偏差。节4,我们提供三个预测调度算法插入空闲时间。节5,大量的实验进行比较三种算法的性能。论文的最后,我们给出一个总结和未来工作的讨论部分6。

2。问题公式化和符号

问题陈述如下。让表示一组单个机器上要处理的工作。我们使用表示工作的处理时间,。这台机器可以处理在同一时间只有一个工作没有抢占和处理工作。一旦处理工作的开始,这台机器是占领,直到完成过程。这台机器随机故障。主要的目标是最小化总完工时间。在这个模型中,我们不仅要优化的主要目标,但也总完工时间偏差之间的预测计划,实现计划。表示预测计划和为实现计划。让表示工作的完成时间在预测的时间表,让表示工作的完成时间在实现的时间表。我们定义总完工时间的预测计划和总完工时间的安排实现的。让是一个预测安排尽量减少没有机器故障,让主要目标被插入一个预测安排空闲时间。

3所示。预赛

在本节中,我们发展一个代理的可预测性,这将在后面的部分。

让工作被索引的顺序出现在预测计划。我们评估预测计划的可预测性总完工时间的预测计划,实现计划之间的偏差。这是计算的 在哪里和(9]。低价值的总时间偏差意味着安排具有更好的预测性能。因此,它可以生成预测计划和更好的预测性能最小化总完工时间偏差。然而,很难优化可预测性的性能,因为随机机器故障。梅塔和Uzsoy9)提出了五个代理可预测性评估完成时间偏差的措施。根据计算的实验中,他们显示代理措施提供相关的预计完成时间偏差显著高于其他措施。因此,我们选择作为替代措施的可预测性。代理措施定义如下: 在哪里安排由增加处理时间的工作吗通过在保持相同的序列,是平均速度机器故障发生,然后呢平均修复时间。

Adiri et al。3和李和河口14]证明了单机调度问题最小化总完工时间与一个非完全多项式分解在一个确定的环境。因此,预测调度优化的总完工时间和可预测性与随机机器故障是相当难以解决。

4所示。启发式预测调度方法

在本节中,三个启发式预测算法开发。节4.1,一个优化代理测量启发式算法的目的是建立一个预测计划。节4.2基于线性规划的启发式算法,预测计划提供。节4.3反馈算法。

为了保持高可预见性的安排与主要目标小牺牲性能,我们使用右移位重新安排机器故障发生后(RSR)方法。右移位延期方法意味着乔布斯开始时间是右移的机器故障,同时保持工作序列预测计划。

4.1。SPT-OSMH算法

梅塔和Uzsoy9]提供了一个优化的替代测量启发式(OSMH)预测调度工作的商店以最小化最大迟到。OSMH启发式,预测计划生成最小化主要目标假设没有故障。然后保持同样的工作顺序和插入空闲时间最小化的时间表而不考虑对主要目标的影响。使用OSMH的概念,我们设计SPT-OSMH预测调度算法在单个机器上总完工时间最小化。SPT-OSMH算法给出的。

算法H1

一步1。生成预测计划最小化使用最短处理时间优先(SPT)规则假设没有机器故障。

一步2。计算工作的空闲时间。生成预测计划通过插入空闲时间成在保持相同的工作顺序,。

一步3所示。使用右移位机故障发生时重新安排方法。

4.2。基于线性规划算法

梅塔和Uzsoy4)提出了一种基于线性规划的启发式在单个机器上预测调度与释放时间最小化最大迟到。基于线性规划的启发式,预测的时间表也生成最小化主要目标假设没有故障。但插入空闲时间的数量是受到一个线性编程控制实现计划主要目标退化。利用基于线性规划算法的概念,我们提供H2预测调度算法以最小化总完工时间。

算法H2

一步1。生成预测计划最小化使用最短处理时间优先(SPT)规则假设没有机器故障。

一步2。计算完成时间的线性规划(LP),同时保持相同的序列。预测的时间表是获得。

一步3所示。使用右移位重排方法机器故障发生时:

让表示工作的完成时间在调度算法获得的H1。约束(3)保证优先级关系。约束(5)在实现进度控制降解。我们定义作为控制参数。

4.3。反馈算法

由算法生成的初始序列H1和H2都优化总完成时间不考虑随机机器故障。序列的预测计划不会改变插入后的空闲时间安排。为了考虑反馈效应的空闲时间初始序列,我们提出H3的反馈算法。

算法H3

一步1。生成预测计划最小化使用最短处理时间优先(SPT)规则假设没有机器故障。

一步2。计算空闲时间的工作,H2的LP优化算法。

一步3所示。插入在时间表。在不减少的顺序安排工作并生成新的预测计划。

一步4所示。使用右移位机故障发生时重新安排方法。

在下一节中,计算实验进行的预测调度问题。

5。实验结果

为了检查的性能预测时间表,一系列的计算实验使用随机生成的测试问题。这些算法在Matlab编写,运行在2.66 GHz的英特尔核心四个人电脑CPU和4.0 GB RAM。测试实例生成的(4]。有六个层次的就业数据;。处理时间从两个离散均匀分布,在那里=(11)和制服=制服(4、8)。因此,我们一共有12个问题参数组合。对于每个问题参数组合,生成20个实例。总共有240实例问题集(见表1)。

的机器故障间隔时间服从指数分布的意思,在那里处理时间和预计的工作。更高的价值表示不太常见的机器故障。机器故障持续时间之间产生一个均匀分布和。6种类型的机器故障参数组合生成(见下表2)。让控制参数是0.5。因此,我们有240个实例主题6类型的机器故障和1440的组合问题和故障类型。

对于每个实例,预测计划是由算法生成的H1, H2, H3。我们模拟执行每个预测计划30倍来计算平均完成时间偏差和平均实现进度总完成时间使用右移位发生机器故障时重新安排方法。让和表示平均完成时间偏差和平均实现计划使用预测算法对问题问H。表示和的平均完成时间偏差和平均实现计划使用predictive-reactive算法(即对问题问。,schedule the jobs in SPT order without inserting idle times) and right-shift rescheduling method. We define的平均百分比总完工时间偏差的改进为同一类问题和的平均百分比总完成时间的改善同样的问题类(正值表示改进而负值意味着退化)。问题类被定义为一组实例,其中一些参数有一个固定值。让表示问题类的地方代表了故障类型,代表的工作,代表了处理时间。让表示参数的所有可能的值。例如,显示与处理时间所有实例的集合:

表3和4分别显示和值为各种问题类。算法的运行时间没有报告以来的大多数实例在几秒钟内完成。根据表3和4,我们可以得出的结论如下。(我)由算法生成的预测时间的可预测性H1, H2, H3在那些没有插入空闲时间明显改善。与此同时,插入空闲时间牺牲小商店的性能。(2)有效地预测调度算法获得的H2控制目标退化,由算法明显优于H1。当B1机器故障的类型,B4, B5,预测方法H2收益率显著改善可预测性在PRS的成本非常轻微的退化的性能实现的时间表。此外,更多的工作表明更高的预测时间的可预测性。(3)由算法生成的可预见性和商店性能H3 H2都比这更好。这表明预测进度由反馈算法认为空闲时间的影响,基于初始序列可预见性和商店的性能有很大的优势。

6。结论

在本文中,我们解决单台计算机预测调度使用空闲时间。性能和稳定性的措施,我们优化的总完工时间和日程安排的可预测性。

预测的时间表在制造系统中扮演重要角色,它应该生成作为规划活动的基础。我们提供三个启发式预测调度算法的单机调度问题。关键的启发式的策略是插入空闲时间。实验结果表明,预测计划提供了重要的可预测性与小牺牲店性能的改善。反馈算法具有可预测性和商店的性能。

对于未来的研究,我们可以考虑的几个扩展预测调度。首先,有趣的是复杂的机器环境制定调度算法问题,如流水车间和开店机环境。第二,我们可以考虑其他的中断。可以处理新工作移民,移民工作,处理时间变化,到期日期的变化预测调度问题。此外,可以使用概率分析得到空闲时间的长度。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

作者要感谢那些评论家的建设性的建议和帮助。这项研究支持由中国自然科学基金会(授予号。71071008和71071008),中国学术委员会和创新的基础北航的博士毕业生。

引用

1. p•布鲁克调度算法施普林格,柏林,德国,第五版,2006年版。
2. m·福瑞调度:理论、算法和系统新世纪,恩格尔伍德悬崖,新泽西,美国,1995年。视图:MathSciNet
3. Adiri, j .布鲁诺·e·佛罗斯特,a . h . g . Rinnooy菅直人“单机流时间调度与单个故障”,Acta Informatica,26卷,不。7,679 - 696年,1989页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
4. 美国诉梅塔和r . Uzsoy预测调度的一台机器故障,”国际期刊《计算机集成制造,12卷,不。1,15-38,1999页。视图:出版商的网站|谷歌学术搜索
5. x荣,y, r .阴,j .张“紧急车辆调度的鲁棒优化方法。”数学问题在工程ID 848312条,卷。2013年,8页,2013。视图:出版商的网站|谷歌学术搜索|MathSciNet
6. d .备忘录和w·赵”,一个不规则的飞行调度模型和算法根据不确定性理论,“应用数学学报ID 361926条,卷。2013年,8页,2013。视图:出版商的网站|谷歌学术搜索|MathSciNet
7. k·n·麦凯,f . r . Safayeni和j . a . Buzacott“调度器的知识的不确定性:缺失的环节,”基于知识的生产管理系统爱思唯尔,阿姆斯特丹,荷兰,1989年。视图:谷歌学术搜索
8. 顾h·l . Liu y, y . g . Xi”健壮和稳定的单机调度随机机器故障,”国际先进制造技术杂志》上没有,卷。31日。7 - 8,645 - 654年,2007页。视图:出版商的网站|谷歌学术搜索
9. 美国诉梅塔和r . m . Uzsoy”预测调度工作车间故障,”IEEE机器人和自动化,14卷,不。3、365 - 378年,1998页。视图:出版商的网站|谷歌学术搜索
10. r .,马路,r . Uzsoy和k·n·麦凯,“可预测的调度单台机器故障和敏感的工作,“国际期刊的生产研究,37卷,不。18日,第4233 - 4217页,1999年。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
11. h . Aytug m·a·罗莉k .麦凯和r . Uzsoy”执行生产计划的不确定性:回顾和未来的发展方向,”欧洲运筹学杂志》上,卷161,不。1,第110 - 86页,2005。视图:出版商的网站|谷歌学术搜索|MathSciNet
12. d . Briskorn j .梁和m .福瑞”鲁棒调度在单个机器上使用时间缓冲,”国际教育协会事务,43卷,不。6,383 - 398年,2011页。视图:出版商的网站|谷歌学术搜索
13. r .亮氨酸和w . Herroelen机器调度的复杂性与一个中断工作,稳定”行动研究快报,33卷,不。2、151 - 156年,2005页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
14. c·李和s . d .河口“单机流时间调度与计划的维护,Acta Informatica卷,29号4、375 - 382年,1992页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet

版权

版权©2014 Hongli朱和香港。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。