一类资源费用可变的平行机排序问题

2017-07-05窦文卿范静

上海第二工业大学学报 2017年2期

窦文卿,范静

一类资源费用可变的平行机排序问题

窦文卿,范静

(上海第二工业大学理学院,上海201209)

研究了资源费用可变的排序问题起源于服务系统和某些特定的生产系统,在这些服务系统中均存在着随着资源使用时段的不同而产生不同的费用。在资源费用可变的排序问题中,工件具有整数加工时间,工件在加工过程中允许中断。假定把机器的时间窗口划分为T个单位时间段,在某个时间段使用机器加工工件就要付出相应的费用,要求在给定的时间窗口内加工完所有的工件。问题的目标函数是经典排序的目标函数与所使用的总资源费用之和。对于目标函数为完工时间和与所使用的总资源费用之和的排序问题,给出了2个近似算法。

排序;平行机;资源费用;可中断

0 引言

在经典的排序模型中考虑的目标函数是Cmax、∑Cj、Lmax、Tmax、∑Uj等。经典的排序模型不考虑资源的使用费用,这是因为经典的排序模型均来源于生产与制造管理,而在制造业中用于工件处理的机器设备均为固定投资,一旦投资购买即为固定成本。然而在许多服务系统中,均存在着随着资源使用时段的不同而产生不同的费用。把资源的使用费用集成到排序与调度模型中,研究可变资源使用费用的排序问题,对于提升服务系统的绩效非常重要。由于资源的使用费用随时间段的变化而变化,故可假定把机器的时间窗口划分为T个单位时间段,在某个时间段使用机器加工工件就要付出相应的费用,要求在给定的时间窗口内加工完所有的工件。问题的目标函数就变为经典排序的目标函数与所使用的总的资源费用之和。

排序与调度模型和算法一直是运作管理、运筹学和计算机科学领域的重要研究课题。经过多年发展,经典的排序与调度模型和算法已经非常成熟,并得到广泛的应用,显著增加了经济效益以及社会效益[1-2]。近年来,又出现了许多新型的排序与调度问题,比如：供应链排序、分批排序等。尽管对服务系统的运作排序与调度模型、算法和应用方面的研究有了一定的进展,但随着社会的进步与发展,相关的研究工作不管是在理论还是应用方面均显不足。本文要研究的内容是如何把资源的使用费用集成到排序与调度模型中,国内外与本文相关的文献不多,对该类问题的研究尚属起步阶段。

从目前的文献可以看出,对于考虑资源使用费用的排序与调度的研究大多考虑的是资源的启动费用[3-6]。与上述研究不同,Dogan等[7]研究了智能电网中独立工作的排序问题,考虑了随时间变化的资源使用费用,其目标是满足各种服务要求。Wan等[8]考虑的是存在时变资源使用费用的单机排序与调度模型,讨论了所有正则目标函数和各类不同条件下模型的计算复杂性和求解方法,证明了资源费用结构为一般情形时,模型是难以求解的,并对一类重要特例(资源费用为时间单调函数的情形)给出了多项式或拟多项式动态规划算法,这类模型在服务系统的运作排序与调度中具有重要意义。Zhong等[9]沿着这一方向,考虑了排序的目标函数为Cmax的模型,证明了问题是难解的并对一类特例给出了多项式时间算法。Zhao等[10]研究了存在时变资源使用费用的2台机器的排序模型,工件在加工过程中不可中断,证明了当资源费用按照特定的模式(包括线性递减、凹递减和凸递减)递减时问题是可以多项式时间可解的。但是他们研究的资源使用费用随时间变化的排序问题都未能考虑服务运作中的众多约束条件。在上述所有的研究中,几乎没有考虑服务系统其他特征的模型(例如在线处理、可中断处理过程等),而且只有Zhao等[10]对算法进行了研究。

本文着重对目标函数为完工时间和与使用的总资源费用之和的工件可中断的平行机排序进行了分析,并给出了2个近似算法。

1 问题介绍

现有n个工件{J1,J2,···,Jn}要在m台机器上加工,其中每个工件Jj具有整数加工时间pj,工件在加工过程中允许中断;由于资源的使用费用随时间段的变化而变化,故可假定把机器的时间窗口划分为T个单位时间段,其中第t个单位时间段是从时刻t-1到t的时段(t=1,2,···,T),πkt表示使用第k台机器的第t个单位时间段所需的资源费用(k=1,2,···,m,t=1,2,···,T),要求在给定的时间窗口内加工完所有的工件;目标函数是经典排序的目标函数f与所使用的总的资源费用之和π,其中f为Cmax、∑Cj、Lmax、Tmax、∑Uj等。令集合Sk表示第k台机器上用来加工工件的时间段(k=1,2,···,m),则总的资源使用费用。由于一个工件不可能同一时间在两台机器上加工,故为了确保可行性,假设本文考虑的排序模型的目标函数为Cj+π,用三参数法可分别表示为

2 问题的近似算法

对于上述问题,先分析最优解的性质,然后寻求问题的算法。

2.1近似算法CS

引理如果问题Pm|slot cost,pm tn|Cj+π存在最优解,那么在其最优解中,每台机器上的工件的加工顺序应该是服从SPT序的。

因此,按照上述引理,本文采用安排工件顺序→选择时间段的思想来设计算法。由于问题Pm|pm tn|∑Cj已经证明是多项式时间可解的,可以用SPT规则求解。

SPT规则将加工时间最小的工件安排到最早空闲的机器上加工。

经过上述分析可提出算法CS。

算法CS执行步骤如下：

(1)先不考虑时间段费用,利用SPT规则得到Pm|slot cost,pm tn|∑Cj的一个排序π′,同时计算排序π′中工件的最大完工时间Cmax;

(2)若Cmax＞T,则此算法无解;若Cmax≤T,则跳转到步骤3;

(3)将时间段按照其费用的非减序排列;

(4)对于Cmax≤t≤T,从每台机器的前t个时间段中选择费用最小的若干个时间段,将工件按照第1步得到的排序π′顺序不变放到选出的时间段上加工,并计算完工时间和(记为C(t))以及所使用的资源费用π(t);

定理1算法CS可在O(n log n+m T2)时间内得到问题的解。

2.2近似算法Π

所研究问题Pm|slot cost,pm tn|∑Cj+π的目标函数有两部分,算法CS的设计思想是让∑Cj尽量小,但是这样会导致使用的资源费用比较高。由于一个工件不可能同时安排在两台机器上加工,故使用的资源费用比较高的原因是选择的时间段比较多,尤其是实例中包含了某个(或某几个)加工时间比较大的工件时。所以,要想降低使用的资源费用,就必须让排序π′中的Cmax尽可能的小,利用该思想设计算法Π如下。

算法Π把算法CS第1步中对工件的预排序所依据的规则稍作改动,先把pj比较大的工件(加工时间大于的工件)单独安排在一个机器上,剩余工件按照SPT规则安排在剩余机器上。

显然,算法Π与算法CS的时间复杂性相同。

定理2 L+V是问题Pm|slot cost,pm tn|∑Cj+π(S)的一个下界。

2.3特殊情形

从算法CS的设计可以看出,工件加工时间差别越小,算法CS的性能就越好。显然,当所研究的问题为Pm|pj=1,slot cost,pm tn|Cj+π,即所有工件的加工时间都为单位时间时,算法CS是一个最优算法,即：

定理3算法CS可得到问题Pm|pj=1,slot cost,pm tn|∑Cj+π的最优解。

3 结语

本文研究了一类考虑可变资源使用费用的工件加工过程可中断的平行机排序问题,目标函数为Cj+π,其中π是所使用的总资源费用。对于该排序问题,本文给出了2个近似算法。下一步将研究目标函数Lmax+π等的可中断的平行机排序或不可中断的排序问题的算法。

[1]PINEDO M L.Scheduling：Theory,algorithms and systems[M].4th Edition.Berlin Heidelberg：Springer,2012. [2]BLAZEW ICZ J,ECKERKH,PESCHE,etal.Scheduling computers andmanufacturing processes[M].2nd Edition. Berlin Heidelberg：Springer,2001.

[3]CAO D,CHENM,WAN G H.Parallelmachine selection and job scheduling tom inim izemachine costand job tardiness[J].Computersand OperationsResearch,2005,32(8)：1995-2012.

[4]LEE I.Artificial intelligence search methods for multimachine two-stage scheduling w ith due date penalty,inventory,andmachining costs[J].Computers&Operations Research,2001,28(9)：835-852.

[5]LEUNG JY T,LEEK,PINEDOM L.Bi-criteria schedulingw ithmachine assignment costs[J].International Journalof Production Economics,2012,139(1)：321-329.

[6]PANWALKAR S S,LIMAN S D.Single operation earliness-tardiness scheduling w ith machine activation costs[J].IIE Transactions,2002,34(5)：509-513.

[7]DOGAN A,OZGUNER F.Scheduling independent tasks w ith qos requirementsin grid computingw ith time-varying resource prices[C]//InternationalWorkshop on Grid Computing.Berlin Heidelberg：Springer,2002：58-69.

[8]WANGH,QIX T.Schedulingw ith variable timeslotcosts [J].NavalResearch Logistics,2010,57(2)：159-171.

[9]ZHONG W Y,LIU X L.A single machine scheduling problem w ith timeslotcosts[M]//Recentadvancesin computer science and information engineering.Berlin Heidelberg：Springer,2012：677-681.

[10]ZHAO Y C,QIX T,LIM M.On scheduling w ith nonincreasing time slot cost tominim ize totalweighted completion time[J].Journalof Scheduling,2016,19(6)：759-767.

A Classof ParallelM achine Scheduling Problem w ith Varible Time SlotCosts

DOUWenqing,FAN Jing
(Schoolof Science,ShanghaiPolytechnic University,Shanghai201209,China)

Thescheduling problem w ith variable timeslotcostsstudied isoriginated from servicesystem and certain production systems, inwhich the resourceusage costs variesover time period.In the scheduling problem w ith variable time slotcosts,an integer processing time is given for each job the jobs and preemption is allowed.Suppose that the planning horizon consists of T time slotsw ith unit length,the corresponding costmustbe paid if some time periods is taken to process jobs,and all the jobsmustbe processed in thegiven time horizon.The objective function is one traditional performancemeasure plus the total time slot costs.For the scheduling problem w ith the total completion time plus the total time slotcosts,two approximation algorithmswaspresented.

scheduling;parallelmachine;slotcosts;preemption

O223

1001-4543(2017)02-0128-03

10.19570/j.cnki.jsspu.2017.02.009

2016-12-01

范静(1979—),女,山西长治人,副教授,博士,主要研究方向为排序论。E-mail：fanjing@sspu.edu.cn。

上海第二工业大学青年教师培养科研项目(201515)资助