当前位置:首页理工论文其它理学论文 → 文章内容

带无向环优先级的单机总加权完成时间调度问题

减小字体 增大字体 作者:轩华  来源:本站整理  发布时间:2013-6-27 18:37:10


  【摘要】单机调度是生产调度领域的一个经典问题,研究了工件间有加工优先级要求的单机总加权完成时间调度问题,考虑了若将工件优先级关系构成的优先级图视为无向图,包含有环的情况。针对该问题,设计了结合双向动态规划的拉格朗日松弛算法进行求解,使得可以求解一个工件可能有多个紧前或紧后工件的情况。大量实验测试结果表明,该算法能够在较短时间内得到令人满意的近优解。 

     关键词:单机总加权完成时间问题;无向环优先级;拉格朗日松弛;双向动态规划

    2.China Golden Materials Corporation,Beijing 100011,China)【Abstract】Single machine scheduling is a classical problem in production scheduling.We study a singlemachine scheduling problem with processing precedence of jobs where cycles may exist if the precedencerelations of jobs are viewed as an undirected graph.The objective is to minimize the total weightedcompletion time of jobs.Lagrangian relaxation combined with hybrid backward and forward dynamicprogramming is applied to solve this problem in order to deal with the case with multiple immediatepredecessors or successors for a job.Experimental results show that this method can obtain satisfactorysolutions within a shorter running time.

    Key words

    :single machine total weighted completion time scheduling;

    undirected cycle precedence;

    单机调度不仅是调度问题中最简单的一类问题,也是调度问题中最重要的一类问题。理论上通常把单机调度作为复杂调度系统的一个子系统,实际生产中比较复杂的调度问题也可以分解为多个单机问题来解决,研究单机调度问题可以帮助理解和解决更为复杂的多机调度问题。对单机的合理调度有助于实现资源的合理分配、降低成本、提高生产效率和设备的利用率,因而对其进行研究具有十分重要的实际意义。

    单机总加权完成时间调度是单机调度中的一个经典问题。在激烈的市场竞争中,能够在最短的时间内完成客户的订单可以有效提高一个企业的竞争力,因此,最小化1||∑wiCi调度问题受到了广泛关注。

    Yuan

    等[1]已证实1|prec|ΣwiCi是NP-hard,因此,本文所研究的更复杂的调度问题1|prec|ΣwiCi也是NP-hard(其中,prec表示可能1个或多个工件41 8    系 统 管 理 学 报第22卷C14∈{25,26,27,28,29,30,31}C15∈{25,26,27,28,29,30,31}(3)从最后一个工件开始向前计算,由R15=Ф和Q15=Ф,可得:Z15(C15)= L15(C15)=w15×C15+∑C15k=C15-p15+1ukZ15(25)=50, Z15(26)=52, Z15(27)=54Z15(28)=56, Z15(29)=58, Z15(30)=60Z15(31)=62(4)由R14=Ф和Q1 4=Ф,得:Z14(25)=50, Z14(26)=52, Z14(27)=54Z14(28)=56, Z14(29)=58, Z14(30)=60Z14(31)=62(5)由R13=Ф和Q1 3=Ф,得:Z13(24)=72, Z13(25)=75, Z13(26)=78Z13(27)=81, Z13(28)=84, Z13(29)=87Z13(30)=90, Z13(31)=93(6)由R12=Ф和Q12=Ф,得:Z12(26)=52, Z12(27)=54, Z12(28)=56Z12(29)=58, Z12(30)=60, Z12(31)=62(7)由R10=Ф和Q10={11},得:Z10(19)=38, Z10(20)=40, Z10(21)=42(8)由R11={10,11,12,13,14,15}和Q11={12,13,14,15},得:Z11(C11)=w11C11+∑{12,13,14,15}min{Cj}Zj(Cj)+∑{10,12,13,14,15}min{C }jZj(Cj)Z11(23)=3×23+ min{25,26,27,28,29,30}Z12(C12)+min{23,24,25,26,27,28,29,30}Z13(C13)+ min{24,25,26,27,28,29,30}Z14(C14)+min{25,26,27,28,29,30}Z15(C15)+ min{19,20}Z10(C10)=331(9)由R9={11}和Q9={11},得:Z9(18)=54+ min{22}Z11(C11)=385Z9(19)=57+ min{22}Z11(C11)=388Z9(20)=60+ min{22}Z11(C11)=391Z9(21)=63+ min{22}Z11(C11)=394(10)R7=Ф和Q7={8},得:Z7(12)=24, Z7(13)=26(11)由R8={7,9},Q8={9},得:Z8(16)=48+ min{12,13}Z7(C7)+ min{17,18,19,20}Z9(C9)=457(12)由R6={8},Q6={8},得:Z6(11)=33+min{16}Z8(C8)=490Z6(12)=36+min{16}Z8(C8)=493Z6(13)=39+min{16}Z8(C8)=496(13)由R2=Ф和Q2={5},得:Z2(1)=2, Z2(2)=4, Z2(3)=6, Z2(4)=8Z2(5)=10, Z2(6)=12, Z2(7)=14, Z2(8)=16(14)由R3=Ф和Q3={5},得:Z3(3)=6, Z3(4)=8, Z3(5)=10Z3(6)=12, Z3(7)=14, Z3(8)=16(15)由R4=Ф和Q4={5},得:Z4(2)=4, Z4(3)=6, Z4(4)=8, Z4(5)=10Z4(6)=12,Z4(7)=14,Z4(8)=16(16)由R5={2,3,4,6,}和Q5={6},得Z5(10)=30+ min{3,4,5,6,7,8}Z3(C3)+ min{2,3,4,5,6,7,8}Z4(C4)+min{10}Z6(C6)=532(17)由R1=Ф和Q1={5},得:Z1(2)=6+min{10}Z5(C5)=538Z1(3)=9+min{10}Z5(C5)=541Z1

[1] [2] [3] [4]  下一页