作业车间调度问题的随机邻域交换算法.docx

作业车间调度问题的随机邻域交换算法.docx

《作业车间调度问题的随机邻域交换算法.docx》由会员分享，可在线阅读，更多相关《作业车间调度问题的随机邻域交换算法.docx（11页珍藏版）》请在冰点文库上搜索。

作业车间调度问题的随机邻域交换算法

第25卷第1期2010年2月　　　　　　　　　　　系　统　工　程　学　报JOURNALOFSYSTEMSENGINEERING　　　　　　　　　　　　　　

Vol.25No.1

Feb.2010

doi:

10.3969/j.issn.1000-5781.2010.01.019

作业车间调度问题的随机邻域交换算法

①

崔健双,李铁克

（北京科技大学经济管理学院,北京100083

摘要:

针对作业车间调度问题提出了一种随机邻域交换算法RNSA（randomneighborhoodswappingalgorithm.

算法由几个紧密衔接的执行阶段组成,其核心思想是如何设计生成多样性调度以及如何判断新调度的可行性.为此,采用了一种组合随机邻域交换策略并证明了一个调度可行性判定定理.为了验证算法的有效性,对一批Benchmark算例进行了测试并与国内外现有研究结果做出了比较.

关键词:

作业车间调度问题;随机邻域交换;关键路径算法中图分类号:

TP273.1　　　文献标识码:

A　　　文章编号:

1000-5781（201001-0111-05

Randomneighborhoodswappingalgorithmforjobshopschedulingproblem

CUIJian2shuang,LITie2ke

（SchoolofEconomicsandManagement,UniversityofScience&TechnologyBeijing,Beijing100083,ChinaAbstract:

Arandomneighborhoodswappingalgorithm（RNSAispresented.Thealgorithmiscom2posedofseveralinterrelatedphases.Itskeyideasarehowtogeneratediversifiedsolutionsandhowtojudgeifthenewsolutionsarefeasible.Fordoingthat,weputforwardarandomneighborhoodswappingpolicyandproveatheoremwhichindicatesthecalculabilityofasolutionisthesufficientandnecessaryconditionforitsfeasibility.Finally,thealgorithmwastestedwithabatchofBench2markproblemsandcomparedwithexistingalgorithms.Keywords:

jobshopschedulingproblem;randomneighborhoodswapping;criticalpathalgorithm

0　引　言

作业车间调度问题是关于多类机调度问题的一类重要组合优化问题.文献[1]系统地总结了这类问题的研究进展.其中,采用遍历搜索的方法由于受时间和资源的限制难以有大的突破,而通过诸如邻域搜索[2]、混合遗传[3-5]、转移瓶颈加禁忌搜索[6-7]

等近优求解算法是目前研究热点.

本文提出的算法就属于一种近优求解算法.算法的核心思想是如何设计生成多样性调度以及如何判断新调度的可行性,为此,采用了一种组合

随机邻域交换策略来生成新的调度并证明了一个可行性判定定理来剔除不可行调度.对于不可行调度立即予以淘汰,以节省计算时间;对于可行调度则再利用关键路径算法做反复地局部优化,逐步逼近最优值.

1　问题模型

设J={Ji}ni=1、

M={Mk}m

k=1分别代表由n个工件和m台机器组成的有限集合.工件Ji必须按照预先指定的顺序Oi1,Oi2,…,Oim（优先顺序约

①收稿日期;修订日期5基金项目国家自然科学基金资助项目（:

2007-10-27:

2009-11-1.

:

70771008.

束在各台机器上依序加工.其中,O

ik表示工件J

i

在机器Mk上一次不可中断加工且加工时间pik是

已知的.同一个工件同时只能被一台机器加工,而同一时间一台机器只能加工一个工件（资源约束.若以Cik代表工件Ji在机器Mk上加工完成的时间,则最后一个工件在最后一台机器上加工完成的时间称为最大完工时间C

max

即makespan.设A代表受优先顺序约束限制的相邻工序对的集合;Ek代表在机器k上加工并且受资源约束限制的工序对的集合.要求在满足优先顺序和资源约束条件下,对各个工件加工顺序进行调度排序并确定这些工件在各台机器上的开工时间rtik≥0,

以使得C

max

最小化,数学模型如下.

Min{C

max}=Min{max（rt

ik

+p

ik

}（1

s.t.　rtjk-rtik≥pik,Π（i,j∈A（2

rtjk-rt

ik

≥p

ik

或rt

ik

-rt

jk

≥p

jk

　　　　　　Π（i,j∈E

k

（3

rtik≥0（4其中,式（2表示Jj必须在Ji之后加工（优先顺序约束;式（3要求同一台机器同时只能加工一个工件（资源约束;式（4说明准备时间为0.

2　初始调度

计算开始于一个初始调度.首先对每个工件按照其加工工序从小到大依次编号.在不考虑机器资源冲突的前提下,每个工件的第0道工序开工时间为0,其它后继工序的开工时间等于其前道工序结束时间,得到各道工序的开工时间,即无资源约束的最早开工时间.然后利用下述规则获得一个初始调度.

定义1　开工顺序优先指派规则

把需要在同台机器上加工的工件放在一起进行开工顺序优先指派,规则如下:

1无机器约束最早开工时间小的优先;2若1相同,加工工序编号小的优先;3若1、2都相同则工件序号小的优先.3　计算makespan并做可行判断

Makespan的计算原则是:

在给定调度下,根据当前机器和工件的空闲状态,选择最早可能被加工的工件立即开始加工在满足问题所有约束条件的前提下,当前机器上当前工件的最早开工及完工时间可按照如下公式计算

对Πm,m′∈M;q,k∈N,有

rtmq=max{etmk,etm′q}

etmq=rtmq+pmq

（5式中,m、m’代表两台不同的机器,q、k代表两个

不同的工件.rtm

q

表示当前工件q在机器m上最早开工时间,etmq表示最早完工时间,pmq是加工时间.若给定的调度可行,则利用公式（5可以依次计算出每道工序的开、完工时间并最终得到makespan.式（5称为makespan计算公式.

定义2　对于给定调度,若能够按照公式（5计算得到所有操作的开工、完工时间,则该调度是可计算调度.

引理1　一个可计算调度是可行调度.

证明　因给定调度是可计算的,按照定义2,只需遵循公式（5即可得到所有操作的开、完工时间,包括makespan.当在计算过程中由于etmk或

etm′

q

未知而影响到不能计算rtm

q

时,即转向下一台机器的当前工件继续进行计算,直到完成为止.

引理2　一个可行调度是可计算的.

证明　使用反证法,假定可行调度不可计算,则意味着或者etmk或者etm′q是未知的,于是对某些操作来说不能获得它们的开工时间,影响到最终不能计算出makespan,而这与调度可行相矛盾.

由引理1和引理2有下列结论.

定理　一个给定调度的可计算性是其可行的充要条件.

由此,仅需要判断一个给定调度是否能够计算出所有操作的开工时间,即可知晓该调度是否可行.下面对于有M台机器N个工件的作业车间调度问题,给出具体实现步骤:

步骤0　在M台机器中选择第m台作为当前机器;

步骤1　从m中选择当前工件q;

步骤2　判断etmk和etm′q是否都已知:

若已知,令rtmq=max{etmk,etm′q},etmq=rtmq+pmq,qωq+1,转步骤1;否则,转步骤3;

步骤3　判断m=M?

若是,m←0,转步骤4;否则,m←m+1,转步骤1;

步骤4　通过对M台机器一轮循环计算后,比较是否每台机器当前工件编号都无变化若是,做调度不可行标记,算法结束;否则,转步骤5;

步骤5　判断各机器所有工件是否全部计算

—

211

—系　统　工　程　学　报　　　　　　　　　　　　　　　　　第25卷

..

完成.若是,返回最大完工时间makespan;否则,转步骤0.

4　产生新调度并做局部优化搜索

随机邻域交换产生新调度的规则如下:

1交换可发生在同台机器任意两个相邻操作之间,这样可避免产生过多的不可行调度,减少无效交换;

2每台机器每次仅允许发生一次交换;3考虑到多个操作之间存在的隐性耦合关系,以工件号、操作位置和加工步骤等已知参数对交换条件进行限制,满足条件的操作才与其后继操作发生交换.

表1　Benchmark测试用例TA01~TA50测试结果比较

Table1TestresultsandcomparisononBenchmarkproblemsTA01~TA50

问题规模最优

（上界TSSB

[6]RE（%TSAB[7]RE（%SB2GLS5[9]RE（%HPSO[10]RE（%RNSARE（%

TA0115×151********181——124411061236014112420189TA0215×151********10012440.00125501881245010812440100TA0315×151********13312220.33122501571224014912180100TA0415×151********100——119111361180014311750100TA0515×151********14112330174125621611233017412300149TA0615×151********157——124701731248018112390108TA0715×151********108——124411*********612280108TA0815×151********12512200125122201411220012512170100TA0915×151********13312820.63129111331283017112800147TA01015×151********17312591.451266*********18512440.24TA11320×151********188140231161386119913731103TA12320×151********18813770.7314163.5813800.9513770.73TA13320×151********14913772.6113641.6413540.89TA1420×151********10013450.0013611.1913500.3713450.00TA15320×151********157——13833.2913641.8713531.05TA16320×151********174——14184.2613771.2513680.59TA1720×151********130——15193.9014801.2314801.23TA18320×151********11514131.2214332.6514252.0814121.15TA19320×151********12013521.2713763.0713531.3513440.67TA20320×151********13413621.0413983.7113731.8513631.11TA21320×20164416590191——16922.9216792.1316580.85TA22320×20160016231144——16382.3816251.5616181.13TA23320×20155715731103——15942.3815781.3515660.58TA24320×20164616590179——17144.1316641.0916540.49TA25320×20159516060169——16312.2616322.3216000.31TA26320×2016451666112816570.7316983.2216792.0716570.73TA27320×20168016971101——17222.5017121.9016910.65TA28320×20160316221119——16533.1216271.5016201.06TA29320×2016251635016216290.2516390.8616451.2316290.25TA30320×20158416141189　　16212.3416131.8316011.07TA3130×151********14017660.1118092.5517720.4517660.11TA32330×151********15118412.5618402.5118482.9518261.73TA33330×151********13518322.2918442.9618342.4018181.51TA34330×151********193——18983.7718792.7318360.38TA3530×152********100——20100.1520100.1520070.00TA3630×151********133——18743.0218431.3218230.22TA3730×151********13718152.4818464.2318082.0917961.41TA3830×151********14317001.6117625.3217011.6716890.96TA3930×151********11118110.8918221.5018100.8418060.61TA40330×151********10517202.7517494.4817142.3916981.43TA41330×20201820451134——21064.3620712.6320531.73TA42330×20194919791154——20183.5419841.8019781.49TA43330×20185818982115——19464.7419283.7718931.88TA44330×20198320362167——20694.3420392.8220131.51TA45330×20200020211105——20492.4520321.6020211.05TA46330×20201520471159——21154.9620702.7320391.19TA47330×20190319381184——19733.6819582.8919321.52TA48330×2019491996214120012.6720806.7220223.7519791.54TA49330×20196720132134——20464.0220152.4419911.22T533×6515——335656平均相对误差（R%ϖ1111651　注带3表明是目标函数值的上界而非最优值;

　注TSSB、TSB、SB2GLSS,SO为相应文献提出方法的最优值或上界,其相邻列的R为其平均相对误差—

311

—

第1期　　　　　　　　　　　　　崔健双等:

作业车间调度问题的随机邻域交换算法

A00201921972420094.11998.74191.

AE1221142871082

1

2AHPE.

　　根据上述规则,当问题的相关参数满足如下逻辑关系时发生交换:

IF{（seq_num=rOprtAND

[（pro_order

=

rStepOR（job_num

=

sJob]}THEN

O

rOprt

∴O

rOprt+1

其中,seq_num是当前机器上加工工序位置;pro_order是加工工序编号;job_num是工件编号.后两个参数都是确知值.rOprt（≤N-1、

rStep（≤M和sJob（≤N是约定范围的三个随

机数.

如果说产生新调度是全局范围内的调整变化,局部优化搜索就是小幅调整.本文采用的局部优化搜索策略是对文献[8]中的关键路径算法

（CPA的改进.改进的CPA增加了对一个关键块

有3个操作的处理方法,即如果一个块中有3个操作,单独做两两交换并选用二者中较好的结果.

5　算法实现步骤

步骤0　利用优先指派规则产生初始调度,计算makespan作为当前目标函数最优值BestValue;

步骤1　产生一个新调度;

步骤2　判断新调度的可行性:

若可行,转步骤3;否则,恢复原调度并判断是否达到设定循环次数;若是,停止计算并输出最终结果;若否,转步骤1;

步骤3　利用改进的CPA对新调度作局部优化搜索,此时BestValue总是保留最优值,转步骤1.

算法中间临时产生的调度都会经过比较后被淘汰,每次仅保留最优调度,因此空间复杂度可忽略不计.算法的计算量,即时间复杂度主要在步骤2、步骤3.针对此类问题的算法一般采用Benchmark问题计算结果的比较来做出评价.

6　算法效果分析与比较

选择了不同规模的80个Benchmark算例TA01~TA80对算法的效果进行测试.使用C语言编程、主频1.5GHz的IBMThinkPadT40进行

计算.因计算结果中TA51~TA80（除TA55外都达到了目标函数最优值,表1中仅列出了TA01~TA50的计算结果.

由TA系列算例计算结果分析可知:

1近44%的算例可获最优值,前50个算例的平均相对误差为0.82%,是参与比较的所有算法中最低的.2为了体现普遍性和公平性,表1数据是在相同环境下对每个算例进行了5遍测试的平均值.3算法也曾对较容易计算的算例做过计算.例如,对于LA01~LA15和LA31~LA35,在既有环境下,每5个算例一组连续进行计算,每组总计算时间都不超过1s.4对于规模超过2000（N=100,M=20的10个算例TA71~TA80,都能够在较短时间内（平均4.3min得到最优值.5与文献[4-6]中提出的算法计算结果的比较也表明,RNSA算法有明显优势.

7　结束语

本文提出了一种组合条件随机邻域交换算法并证明和编程实现了调度可行判定准则,指出可计算性是调度可行的充要条件.可行判定及时淘汰了无效调度,提高了计算效率.算法还成功地引入了改进的CAP,实现了局部邻域优化搜索,对提高算法的搜索深度起到了重要作用.Benchmark测试用例的计算结果证明了算法的有效性和可靠性.

参考文献:

[]S,MSDj,f[]fOR2

,3（33[]王　磊,黄文奇求解工件车间调度问题的一种新的邻域搜索算法[]计算机学报,5,（56—

411—系　统　工　程　学　报　　　　　　　　　　　　　　　　　第25卷

1JainAeeran.eterministicobshopscheduling:

PastpresentandutureJ.EuropeanJournaloperationalesearch1999112:

90-44.

2.J.20028:

809-81.

WangLei,HuangWenqi.Anewlocalsearchalgorithmforjobshopschedulingproblem[J].ChineseJournalofComputers,2005,28（5:

809-816.（inChinese

[3]JoséFG,JorgeJMM,MaorícioGCR.Ahybridgeneticalgorithmforthejobshopschedulingproblems[J].European

JournalofOperationResearch,2005,167（1:

77-95.

[4]ByungJP,HyungRC,HyunSK.Ahybridgeneticalgorithmforthejobshopschedulingproblems[J].Computers&In2

dustrialEngineering,2003,45（3:

597-613.

[5]FedericoDC,RobertoT,GuiseppeV.Ageneticalgorithmforthejobshopproblem[J].ComputersOperationResearch,

1995,22（1:

15-24.

[6]AdamsJ,BalasE,ZawackD.Theshiftingbottleneckprocedureforjob2shopscheduling[J].ManagementScience,1988,

34（3:

391-401.

[7]FerdinandoP,EmanuelaM.Ataboosearchmethodguidedbyshiftingbottleneckforthejobshopschedulingproblem[J].

EuropeanJournalofOperationalResearch,2000,120（2:

297-310.

[8]NowickiE,SmutnickiC.Afasttaboosearchalgorithmforthejobshopproblem[J].ManagementScience,1996,42（6:

797-813.

[9]BalasE,VazacopoulosA.GuidedLocalSearchwithShiftingBottleneckforJobShopScheduling[R].ManagementScience

Research