同时具有学习和恶化效应的不同工期指派问题研究.pdf

《同时具有学习和恶化效应的不同工期指派问题研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第32卷第3期沈阳师范大学学报(自然科学版)V01．32No．32014年7月JournalofShenyangNormalUniversity(NaturalScienceEdition)Ju1．2o14文章编号：1673—5862(2014)03—0358—06同时具有学习和恶化效应的不同工期指派问题研究王吉波，牛玉萍，刘璐，郭倩(1．沈阳航空航天大学经济与管理学院，沈阳110136；2．沈阳航空航天大学理学院，沈阳110136)摘要：讨论工件同时具有学习和恶化效应的单机排序模型，其中工件的

2、实际加工时间是其基本加工时间、开工时间和所排位置的函数，每个工件都有自己的工期。目标是确定工件的加工顺序和工期，使工件的提前成本、延迟成本和工期的机会成本的加权和最小。证明此问题在工件引入学习和恶化效应后，依然多项式时间可解，同时给出了求解算法和实例来说明如何最优的求解这个问题。关键词：排序；学习效应；恶化效应；工期中图分类号：0223文献标志码：Adoi：10．3969／i．issn．1673—5862．2014．03．0070引言排序问题是一类重要的组合最优化问题，多年来人们一直在运筹学、管

3、理科学、系统工程、计算机科学等领域致力于该问题的研究。在大多数排序问题中，工件的加工时间是一个独立的且与开工时间和加工位置无关的常数。不过，在所知的一些实际问题中，由于工人(机器)在很长的时间加工相同或类似的工件时，加工效率有可能逐渐提高，因而使得后面加工的工件的加工时间缩短，这种现象被称作具有学习效应【】]。另一方面，在实际生产中，工件的实际加工时间会因工件开始时间的推迟而延长，这种现象被称为具有恶化效应_2j。BiskupE、Cheng等E5]首先研究了这类具有学习效应的单机排序问题。在Bi

4、skup的文章中，他证明了在具有学习效应的工件排序情况下，当目标函数为极小化共同工期偏差与完工时间和时，这类单机排序问题是多项式时间可解的。Cheng等E5]研究了工件加工时间具有学习效应的单机排序问题，其中工件的学习效应模型为一个分片线性加工时间函数，目标函数为极小化最大延误时间。他们证明了此问题是强NP一难的，并给出了2个多项式时间可解的特殊情况。同时，还提出了2个启发式算法，并分析了它们的最坏情况界。孙林辉等[6]研究了具有学习效应的流水作业排序问题，对总完工时间极小化问题，给出了数学规划

5、模型和3个启发式算法。MosheiovE]对其他的一些单机排序问题进行了研究，得出了使用最小加工时间优先规则(SPT)可以获得最大完工时间问题的最优排序。BiskupE]对这类具有学习效应的排序问题进行了综述。最近关于学习效应的排序成果，读者可参考文献[9—14]。Gawiejnowic~15]给出了关于工件具有恶化效应排序问题的综述。最近关于恶化效应的排序成果，读者可参考文献[16—19]。Lee首次提出了工件同时具有学习和恶化效应的排序问题模型[，接着WangE2>28]，Low等E9_研究

6、了不同的模型。王吉波等_19_研究了工件具有不同工期的排序问题，其中工件的加工时间具有恶化效应。但现实的生产过程中存在着工件加工同时具有学习效应和恶化效应的情况(WangE21-22]，Wang等[2。])，因此本文收稿日期：2014—05—17。基金项目：国家自然科学基金资助项目(11001181)。作者简介：王吉波(1975一)，男，辽宁沈阳人，沈阳航空航天大学教授，博士，大连理工大学博士研究生导师。第3期王吉波，等：同时具有学习和恶化效应的不同工期指派问题研究359研究工件加工同时具有学习

7、效应和恶化效应的不同工期排序问题，证明了此问题依然多项式时间可解。1问题模型本文考虑如下模型：假定，z个工件J：=={J，J。，⋯，J)要在一台机器上加工，在同一时刻机器最多只能加工一个工件，且机器不允许中断，工件必须连续加工，也不允许中断。同WangEz1]一样，若被排在位置r的工件J(一1，2，⋯，)的开工时间为t，则其实际加工时间为Pj一(口j+)re，其中，a为工件的基本加工时间；≤0为工件的学习率；6≥0为工件的恶化率。对于工件的一个排序(即加工顺序)7c，令—CJ(7c)和分别表示工

8、件J的完工时间和工期。记EJ—max{0，d一)为工件J的提前成本，TJ=max{0，一)表示工件，的延迟成本，A表示所有顾客的期望工期，A—max{0，dj—A}表示工件J，的机会成本(王吉波等]，Seidmann等。。)。目标惩罚函数为最小化提前成本、延迟成本和工期机会成本的加权和，即f(d，7【)一∑(++7AJ)，三参数表示法表示为：J：11IPJ一(ai+)l∑(+pT+7A)其中a，和7分别表示每一时间单元的提前、延误和工期惩罚。2主要结论引理1(Wang[。])对于任意一个给定排序