具有恶化效应的双代理单机最优调度算法

刘岳镭,冯祖仁,任晓栋

(西安交通大学机械制造系统工程国家重点实验室,710049,西安)



具有恶化效应的双代理单机最优调度算法

刘岳镭,冯祖仁,任晓栋

(西安交通大学机械制造系统工程国家重点实验室,710049,西安)

针对单机床加工环境中待加工任务具有恶化效应且来自2个具有不同需求的代理时,无法快速求解出满足要求且成本最低的最优加工序列的情况,提出了可在特定约束条件下的具有恶化效应的双代理单机最优调度算法。首先提出优化目标为:保证一个代理的任务均不延迟完工的前提下,使得另一个代理的总加权完成时间或总加权折扣完成时间最小;其次指出该优化问题具有NP难度,并给出其在一般及特殊情况下最优解的结构性质;此后对于特定约束条件下的情形,提出多项式时间优化算法。该算法中首先将2个代理的任务分别按照所证明的最优策略排序,然后再按照使得2个代理能得到最小总加权完成时间和给定约束关系的算法将2个序列合并在一起,并证明得出的序列即为所求调度问题的最优解。实验结果表明,该算法作为确定性算法,计算时间与最优解平均误差率大于0.3%的模拟退火算法相似,远远低于可求解出最优解的分支定界算法。

调度问题;单机;双代理;恶化效应

不同于经典调度问题,在现实生产环境中,经常会遇到待加工任务来自不同的代理,且任务的加工时间具有恶化效应的情况。在这种复杂情况下,如何同时面对不同代理的不同需求,依然获得任务加工调度的最优解,成为了研究的难点。

1988年,Gutpa提出了一种任务的加工时间是它们开始(等待)时间的单调递增函数的调度问题模型,首次提出了任务加工中的恶化效应[1]。出乎意料的是,这一模型并未得到广泛关注,直到十多年后才有学者对任务加工时间具有恶化效应的不同模型的调度问题进行了详细的描述[2-3]。文献[4]针对最大完工时间、总加权完成时间等优化目标的单机线性恶化调度问题给出了多项式时间算法;文献[5]在引入释放时间的基础上,对特殊约束下的恶化调度问题给出了最优算法。

在此前的调度问题中,大部分待加工任务均来自同一代理,然而实际生产活动中,这一假设可能在某些情况下无效,即需要加工的任务可能来自于多个代理。涉及多个代理的调度问题在近年来成为了一个新兴的研究课题。大量研究者证明了多种调度问题在单机模型下具有NP难度:多代理的优化目标同时为最小化总加权延迟完工任务数或最小化任务最大完成时间[6];保证一个代理最大提前完工时间不超过给定值的前提下最小化另一个代理的最大提前完成时间或加权提前完成时间和[7];最小化一个代理的加权最大完成时间与另一个代理的加权完成时间和的总和[8]等。

直到2010年以后,才有学者将恶化效应引入到双代理问题中来,并取得了一系列研究成果:文献[9]针对一个代理最大延迟完成时间小于给定上界、另一个代理加权延迟完工任务数总和最小的调度问题,提出了分支定界算法和禁忌搜索算法求解最优和近优解;文献[10]讨论一个代理的最大完工时间不超过一个给定上界的约束下,另一个代理的总完工时间最小的调度问题,给出多项式时间最优算法;文献[11-12]分别针对特殊情况下,优化目标关于推迟/提前完工时间的一些调度问题模型,同样给出了多项式时间算法。本文针对单机环境下具有恶化效应的双代理调度问题下的一个模型的多个加权优化目标进行了研究,指出了问题的NP难度,讨论最优解结构特征,并以此为依据给出特定情形下的多项式时间算法。

1 恶化效应的单机双代理问题模型

本文主要讨论单机环境下的以下调度问题:假设存在n个任务,J={J1,J2,…,Jn},来自2个不同的代理X={A,B},n=nA+nB,其中nA和nB分别为来自代理A和B的任务数量。对于每项任务Jj都有初始(基础)加工时间pj,权值wj,交货日期dj以及代理参数Ij,且有当Jj∈A时Ij=0,Jj∈B时Ij=1。考虑到恶化效应,若任务Jj在t时刻开始加工,则实际加工时间为pj(a+bt),其中a>0为给定参数,b≥0为给定恶化参数。对于一个调度解S,任务Jj的完工时间表示为Cj(S),任务Jj的延迟交货时间表示为Tj(S)=max{0,Cj(S)-dj},当Tj(S)>0时有Uj(S)=1,否则Uj(S)=0。

使用α|β|γ三参数表示法[13],本文讨论的问题模型可以分别被写作

(1)

(2)

式中:α域中的1表示单机床加工环境;γ域中的符号∶表示其之前的部分为优化目标,而其之后的部分为需保证的约束条件。

2 优化调度算法

2.1 代理B不延迟且代理A总加权完成时间最小的调度问题

证明 采用数学归纳法证明

引理1得证。

引理3 该问题最优解的任务加工序列中,代理B的任务按照其交货日期dj非降序排列。

引理4 假设有调度解S,其中有2个相邻任务Ji和Jj,其中Ji先于Jj被加工。现将任务Ji与Jj的加工次序互换,得到新的调度解S′,在此基础上假设任务Ji在调度解S中的开始加工时间为t。若Ji,Jj∈A且有wjpi(1+bpj)

证明 任务Ji在调度解S和调度解S′中的加工完成时间分别为

Ci(S)=pi(a+bt)+t

(3)

Cj(S)=pj(a+bCi(S))+Ci(S)=

pi(a+bt)+pj(a+bt)+pipjb(a+bt)+t

(4)

Cj(S′)=pj(a+bt)+t

(5)

Ci(S′)=pi(a+bCj(S′))+Cj(S′)=

pi(a+bt)+pj(a+bt)+pipjb(a+bt)+t

(6)

由此可得

wiCi(S)+wjCj(S)-(wiCi(S′)+wjCj(S′))=

wjpi(1+bpj)(a+bt)-wipj(1+bpi)(a+bt)

(7)

则当wjpi(1+bpj)

引理5 若该调度问题中,代理A的任务具有权值与初始加工时间的反相关约束,则最优解中代理A的任务按照加权最短加工时间优先规则(WSPT)排序(即按照pj/wj非降序排列)。

(8)

对于代理B不延迟且代理A总加权完成时间性最小的调度问题,在来自代理A的任务遵循权值与初始加工时间的反相关约束这一特殊情况下,由引理2、3和5,可给出如下算法。

算法1 代理B不延迟且代理A总加权完成时间最小问题的最优解算法步骤如下。

步骤4 如果i≥1或j≥1,则跳转至步骤2,否则输出加工序列S=(J[1],J[2],…,J[nA+nB]),算法结束。

定理1 如果代理A的任务遵循权值与初始加工时间反相关的约束,则对于该调度问题,算法1可求解出最优解,且其计算的时间复杂度为O(nAlognA+nBlognB)。

证明 算法1中,代理B和代理A的任务分别依照引理3和引理5的方式排序,再根据引理2将2个排序组合为可行解。引理2、引理3以及引理5的证明保障了算法1可以求得最优解。步骤1中关于代理A和代理B的任务排序,其时间复杂度分别为O(nAlognA)和O(nBlognB),故整个算法的时间复杂度为O(nAlognA+nBlognB)。证毕。

2.2 代理B不延迟且代理A总加权折扣完成时间最小的调度问题

引理6 若该调度问题中,代理A的任务具有权值与初始加工时间的反相关约束,则存在一个最优解,其中代理A的任务按照加权折扣最短加工时间优先规则(WDSPT)排序(即按照(1-exp(-rpj))/wjexp(-rpj)非降序排列)。

(9)

由此可得

(10)

这与S为最优解的假设相矛盾,故最优解中代理A的任务按照WDSPT规则排序,证毕。

对于代理B不延迟且代理A总加权折扣完成时间最小的调度问题,在来自代理A的任务遵循权值与初始加工时间的反相关约束这一特殊情况下,由引理2、3和6,可给出如下算法。

算法2 代理B不延迟且代理A总加权折扣完成时间最小问题的最优解算法步骤如下。

步骤4 如果i≥1或j≥1,则跳转至步骤2,否则输出加工序列S=(J[1],J[2],…,J[nA+nB]),算法结束。

定理2 如果代理A的任务遵循权值与初始加工时间反相关的约束,则对于该调度问题,算法2可求解出最优解,且其计算的时间复杂度为O(nAlognA+nBlognB)。

证明 同定理1。

3 仿真结果

为了评估本文给出的具有恶化效应的双代理单机最优调度算法,将其与文献[15]中给出的分支定界算法(B&B)以及模拟退火算法(SA)进行对比。采用的算例与文献[15]生成方式类似,假设2个代理的任务数量相同,分别对应n=10,12,14,a=1,以及不同的恶化参数b=0.002,0.005,在保证代理A的任务遵循权值与初始加工时间反相关的约束的前提下,生成了多组各30个的随机数据。由于本文的2个算法类似,故只针对算法1进行仿真对比。此外,为了与SA算法进行比较,定义如下最优解平均误差率

(11)

式中:SSA表示SA算法得到的近优解;T表示最优解所对应的代理A的总加权完成时间。

表1为3种算法计算时间的对比。从表1中可以看出:B&B算法的CPU时间远大于其他2种算法,这是因为为了求解出问题的最优解,B&B算法需要经历大量节点的计算,并且B&B算法的CPU时间会随着问题规模的小幅增大而剧烈增加;另一方面,SA算法所需计算时间与本文的确定性最优解算法1类似,但却只能在接近的计算时间内获得问题的近优解,且SA算法的解质量的平均误差率也会随着问题规模增加而变大(当n=10时,rerror≈0.3% ;当n=14时,rerror≈1.4% )。

表1 3种算法的计算时间对比

4 结 论

本文针对单机床环境下任务来自2个不同的代理且任务的加工时间具有与任务开始加工时间相关的恶化效应的调度问题,在优化目标为保证一个代理的任务均不延迟完工的前提下使得另一个代理的总加权完成时间或总加权折扣完成时间最小,指出问题具有NP难度,并提出在特定约束条件下的时间复杂度为O(nAlognA+nBlognB)的最优解算法(算法1和算法2)。仿真结果表明:采用本文提出的最优解算法可以高效地求解出满足要求且成本最低的最优加工序列。

虽然本文算法1和算法2仅能对这类问题的特例加以求解,但它们也为一般性问题最优解或近优解算法提供了有效的启发信息。更一般性的问题仍然有待进一步研究与解决。

[1] GUPTA J N D, GUPTA S K. Single facility scheduling with nonlinear processing times [J]. Computers & Industrial Engineering, 1988, 14(4): 387-393.

[2] ALIDAEE B, WOMER N K. Scheduling with time dependent processing times: review and extensions [J]. Journal of the Operational Research Society, 1999, 50(7): 711-720.

[3] CHENG T C E, DING Q, LIN B M T. A concise survey of scheduling with time-dependent processing times [J]. European Journal of Operational Research, 2004, 152(1): 1-13.

[4] 赵传立, 张庆灵, 唐恒永. 具有线性恶化加工时间的调度问题 [J]. 自动化学报, 2003, 29(4): 531-535. ZHAO Chuanli,ZHANG Qingling,TANG Hengyong. Scheduling problems under linear deterioration [J]. Acta Automatica Sinica, 2003, 29(4): 531-535.

[5] 赵晓丽, 唐立新. 带有线性恶化工件和释放时间的2个代理单机调度问题 [J]. 自动化学报, 2015, 41(1): 104-112. ZHAO Xiaoli, TANG Lixin. Two-agent scheduling with linear-deteriorating jobs and release dates on a single machine [J]. Acta Automatica Sinica, 2015, 41(1): 104-112.

[6] CHENG T C E, NG C T, YUAN J J. Multi-agent scheduling on a single machine with max-form criteria [J]. European Journal of Operational Research, 2008, 188(2): 603-609.

[7] MOR B, MOSHEIOV G. Scheduling problems with two competing agents to minimize minmax and minsum earliness measures [J]. European Journal of Operational Research, 2010, 206(3): 540-546.

[8] NONG Q Q, CHENG T C E, NG C T. Two-agent scheduling to minimize the total cost [J]. European Journal of Operational Research, 2011, 215(1): 39-44.

[9] WU Wen-Hsiang, XU Jianyou, WU Wen-Hung, et al. A tabu method for a two-agent single-machine scheduling with deterioration jobs [J]. Computers & Operations Re-search, 2013, 40(8): 2116-2127.

[10]刘鹏, 周晓晔, 荣楠. 带有学习效应和恶化工件的双代理调度问题 [J]. 系统工程学报, 2012, 27(6): 841-846. LIU Peng, ZHOU Xiaoye, RONG Nan. Two-agent scheduling with a learning effect and deteriorating jobs [J]. Journal of System engineering, 2012, 27(6): 841-846.

[11]LIU Peng, YI Na, ZHOU Xiaoye. Two-agent singlemachine scheduling problems under increasing linear deterioration [J]. Applied Mathematical Modelling, 2011, 35(5): 2290-2296.

[12]YIN Yunqiang, WU Chin-Chia, CHENG Shuenn-Ren. Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties [J]. Information Sciences, 2012, 189(7): 282-292.

[13]AGNETIS A, BILLAUT J, GAWIEJNOWICZ S, et al. Multiagent scheduling-models and algorithms [M]. Berlin, Germany: Springer, 2014: 6-16.

[14]YIN Y, CHENG T C E, WAN L, et al. Two-agent sing-le-machine scheduling with deteriorating jobs [J]. Computers & Industrial Engineering, 2015, 81: 177-185.

[15]JIN Y C. Minimizing total weighted completion time under makespan constraint for two-agent scheduleing with job-dependent aging effects [J]. Computers & Industrial Engineering, 2015, 83: 237-243.

[本刊相关文献链接]

董春云,蔡远利.高超声速再入飞行器轨迹优化算法评估策略.2016,50(4):28-34.[doi:10.7652/xjtuxb201604005]

李国梁,张合新,周鑫,等.状态反馈事件触发控制系统的分析与设计.2016,50(5):146-150.[doi:10.7652/xjtuxb201605 022]

李小虎,柳松玮,施虎,等.基于两自由度H∞控制策略的泵控液压系统研究.2016,50(4):7-13.[doi:10.7652/xjtuxb 201604002]

杨航,刘凌,阎治安,等.双闭环Buck变换器系统模糊PID控制.2016,50(4):35-40.[doi:10.7652/xjtuxb201604006]

宋汝君,单小彪,李晋哲,等.压电俘能器涡激振动俘能的建模与实验研究.2016,50(2):55-60.[doi:10.7652/xjtuxb 201602010]

严惠云,张浩磊,刘小民.一种仿生鱼体自主游动的水动力学特性分析.2016,50(2):138-144.[doi:10.7652/xjtuxb2016 02023]

黄博,苑寿同,薛嘉伦.碳纤维气流扰动展纤器展纤过程仿真与实验.2015,49(12):19-25.[doi:10.7652/xjtuxb201512 004]

陈江城,张小栋,李睿,等.利用表面肌电信号的下肢动态关节力矩预测模型.2015,49(12):26-33.[doi:10.7652/xjtuxb201512005]

连峰,王婷婷,韩崇昭.多个不可分辨目标群的联合检测与估计误差界.2015,49(11):89-95.[doi:10.7652/xjtuxb2015 11015]

张蕾,张爱民,景军锋,等.静止无功补偿器与发电机励磁系统的自适应鲁棒协调控制策略2015,49(11):96-101.[doi:10.7652/xjtuxb201511016]

王海龙,王刚,陈曦,等.仿海蟹机器人游泳足水动力学分析与实验研究.2015,49(8):75-83.[doi:10.7652/xjtuxb 201508013]

刘冠初,熊静琪,乔林,等.四足机器人自由步态规划建模与算法实现.2015,49(6):84-89.[doi:10.7652/xjtuxb201506 014]

刘冠初,熊静琪,乔林,等.四足机器人自由步态规划建模与算法实现.2015,49(6):84-89.[doi:10.7652/xjtuxb201506 014]

董恩清,刘伟,宋洋.采用三角形节点块处理无线传感器网络节点定位中节点翻转歧义的迭代方法.2015,49(4):84-90.[doi:10.7652/xjtuxb201504014]

卜祥伟,吴晓燕,张蕊,等.双曲正弦非线性跟踪微分器设计.2015,49(1):107-111.[doi:10.7652/xjtuxb201501018]

(编辑 刘杨)

An Optimal Scheduling Algorithm on Single-Machine with Two-Agent and Deteriorating Jobs

LIU Yuelei,FENG Zuren,REN Xiaodong

(State Key Laboratory for Manufacturing Systems Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

Two-agent single-machine scheduling problems with a deterioration job of which the actual processing time is defined as a function of its starting time are investigated. Optimization algorithms of polynomial time under some certain constraints are proposed. The optimization target of the problem is formulated as to minimize the total weighted completion time or total weighted discounted completion time of one agent while ensuring that all the jobs on the other agents are not delayed. This optimization problem is proved NP-hard and the structural properties of its optimal solutions under general and special conditions are illustrated. Optimization algorithms of polynomial time for solving these scheduling problems are proposed under some constraints. First, the jobs from two agents are respectively sequenced according to their optimal structural properties. Then, they are combined following the strategies that ensure the optimization target of two agents. Simulation results and comparisons with scheduling results of the simulated annealing (SA) and the branch-and-bound algorithms show that the CPU-times of the proposed algorithms are similar with the SA’s that has an error rate greater than 0.3% with the optimal solutions, and much smaller than that of the branch-and-bound algorithm.

scheduling; single-machine; two agents; deteriorating jobs

2015-11-09。 作者简介:刘岳镭(1986—),男,博士生;冯祖仁(通信作者),男,教授,博士生导师。 基金项目:国家自然科学基金资助项目(61203350)。

时间:2016-04-03

10.7652/xjtuxb201606002

TP29

A

0253-987X(2016)06-0009-06

网络出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160403.1822.006.html