考虑运输的退化工件在线排序问题研究

刘其佳，张利齐，冯　琪

(1.郑州大学 数学与统计学院，河南 郑州 450001；2.河南农业大学 信息与管理科学学院，河南 郑州 450003；3.中原工学院 理学院，河南 郑州 450007)

考虑运输的退化工件在线排序问题研究

刘其佳1，张利齐2，冯琪3

(1.郑州大学 数学与统计学院，河南 郑州 450001；2.河南农业大学 信息与管理科学学院，河南 郑州 450003；3.中原工学院 理学院，河南 郑州 450007)

摘要：本文研究了单台机器上工件具有退化效应并且需要考虑工件运输的在线排序问题.目标函数是最小化最大运输完工时间.对于这个在线排序问题，主要是设计一个有效的在线算法.首先采用对手法找到问题的下界，即设计一个坏实例，使得算法得到的目标值与离线最优目标值的比尽可能的大，之后依据下界设计给出一个在线算法.通过对手法的应用，给出问题的下界，并设计了一个竞争比为2的在线算法.

关键词：排序；退化工件；运输

0引言

排序问题是一类重要的优化问题.在经典的排序问题中，所有工件在机器上的加工时间为一个常数.然而在实际问题中，许多工件的加工时间依赖于工件的开工时间.例如：在钢铁企业的生产过程中，工件的加工是有着严格的温度要求的.如果工件在加工前有等待时间，将会引起工件温度下降.这样，必须重新加温到规定的温度才能加工工件，从而导致加工时间变长.再比如，机器长时间加工出现老化现象同时工人的长时间工作会出现疲劳操作，这些都会导致开工晚的工件所需要的加工时间变长.文献[1]和[2]分别独立提出了具有退化效应的排序问题.文献[3]对单机上工件的加工时间是开工时间的简单线性函数的排序问题进行研究.但是在实际问题中，决策者并不能在决策时刻知道工件的完整信息.因此线排序问题受到越来越多人的关注.文献[4]研究了3个工件具有退化效应的在线排序问题，目标函数分别为最小化最大运输完工时间、完工时间和以及最大时间表长.对于这3个问题，作者给出了最好可能的在线算法.文献[5]中工件的加工时间是关于开工时间的简单线性函数，目标函数是最小化完工时间和.对于这个问题，文献[5]给出问题的下界并设计出达到下界的最好可能的在线算法.

近些年，整合生产和运输的在线排序问题也得到了广泛的研究.文献[6]较早的研究了单机上考虑工件运输的在线排序问题，并给出最好可能的在线算法.文献[7]是在批处理机上研究带工件运输的在线排序问题.当批处理机的数目为2和3时，分别给出了竞争比为2的在线算法.当批处理机的数目大于4时，给出竞争比为1.5的在线算法.文献[8]是研究单机上工件需要分批运输的在线排序问题.对于不同的模型，分别给出了在线算法.文献[9]研究了两阶段供应链的半在线排序问题，并给出了有效的算法.在此之前的文献分别研究了退化工件的排序问题以及工件具有运输时间的排序问题，但是并没有很好的将二者结合起来.笔者研究了运输车辆的容量有限制的退化工件的在线排序问题，不仅将二者有效的结合在一起，而且更符合实际生产生活的要求.

1问题的描述

假定工件J1,J2,……,Jn按时间在线到达，即只有工件Jj到达了，才能知道它的到达时间rj及退化率aj.而且工件的数目n也是事先不知道的.我们研究的模型中，工件的退化效应是指pj=ajt，其中t是该工件的开工时刻.工件的加工时间依赖于工件的开工时间，通常假定所有的工件是在某个时刻及之后到达的，假定所有工件是在t0时刻及之后到达的.这些工件先在一台机器上加工，然后完工的工件再由一台容量有限制的车辆运送给下了订单的顾客.目标函数是最小化最大运输完工时间.令T是车辆在机器和顾客之间运送一个来回所花费的时间.由于事先并不会知道谁会下订单，因而假定当第一个工件到达的时刻，才会知道T的大小.我们用Dj表示Jj的运输完工时间，即车辆将Jj由加工地运送给顾客并再次返回到加工地的时刻.这个在线排序问题用三参数表示为

式中：1→D表示工件先在一台机器上加工，完工的工件再被车辆运送给顾客；online,rj≥t0表示这个排序问题中的工件按时间在线到达；pj=ajt表示工件的加工时间依赖于工件的开工时间；v=1,c表示有一台容量限制为c的车辆参与运输，即车辆每次运送的工件数最多为c个；Dmax=max{Dj,1≤j≤n}是目标函数，最大运输完工时间.

在线排序中，决策者是在不知道未来工件信息的情况下设计在线算法的，因此大部分的问题都找不到最优的在线算法.通常我们用竞争比衡量在线算法的好坏，对于最小化目标函数的问题，我们说在线算法A是ρ竞争的，如果对任意实例I有A(I)≤ρ·opt(I)，其中A(I)是在线算法A的目标函数值，opt(I)是最优离线算法生成的目标函数值.研究在线排序问题时，首先要找到问题的下界，通常是用对手法.所谓对手法是指设计一个坏实例，使得任意的在线算法应用到该实例上时得到的目标值与离线最优目标值的比值尽可能大.然后再设计在线算法，而设计算法的竞争比要尽可能的与问题的下界接近，而一旦算法的竞争比与问题的下界吻合，我们称这样的算法为最好可能的在线算法，这样在线问题就得到彻底的解决.

在我们研究的排序问题中，车辆的运输容量是有限制的，这也和实际问题一致.我们将放在车辆上同时运输的工件集合称为一个运输批.令B1,……,Bq是某个排序中按此标号运输的运输批.

U(t): 时刻t已经到达但尚未加工的工件集合；A(s): 时刻s已经完工但尚未被运输的工件集合；ρ(Bi): 运输批Bi的准备时间，即集合Bi里工件的最大完工时刻；δ(Bi):Bi开始被运送的时刻，显然在一个可行排序中，始终有δ(Bi)≥ρ(Bi)；如果δ(Bi-1)+T<δ(Bi)，我们说车辆在紧挨着时刻δ(Bi)之前是空闲的；反之，如果δ(Bi-1)+T=δ(Bi)，我们说车辆在紧挨着时刻δ(Bi)之前是忙碌的；D(Bi): 运输批Bi的运输完工时刻，即D(Bi)=δ(Bi)+T.

2问题的下界

定理1对于排序问题

不存在竞争比小于1+α的在线算法.

进而当k→+∞时，得到

=1+(αt0(1+a1)+αT)/t0(1+a1)+T=1+α.

当k→+∞且ε→0时，有

=1+a1t/(t+kT)≥1+(α(k-1)T)/(t+kT)

→1+α.此定理得证.

3设计在线算法及竞争比分析

3.1算法Dc

加工阶段.在时刻t，如果机器是空闲的且有U(t)≠∅时，从U(t)中选择退化率最小的工件在t时刻加工.否则，只需等待.

运输阶段.

步骤3如果0

①如果机器在时刻s是空闲的且U(s)=∅，把集合A(s)中的工件放在一个运输批并在时刻s运送这个运输批.

②如果机器在时刻s是忙碌的或者U(s)≠∅，需要等待到机器是空闲的且U(s′)=∅的时刻(s′>s)或者等待到有新的工件到达的时刻.

步骤4回到步骤 1.

事实上算法Dc的加工阶段是一个相对独立的算法，只要是有已经到达尚未加工的工件，机器就会一直忙碌.而算法Dc的运输阶段则是要依赖于是否有一定数目的已经完工尚未被运送的工件.运输阶段中机器是空闲的说明此刻没有工件正在加工，而U(s)=∅说明此刻没有已经到达但尚未加工的工件.当需要运输的工件的数目不超过c个时，必须同时满足以上两个条件，车辆才有可能开始运送工件.

证明：引理 1.中的贪婪算法是指在存在已经到达且尚未加工的工件时，算法可以按照任意的顺序将工件安排在机器上的加工.由此算法Dc的运输阶段就是一个贪婪算法，依据引理1知道μ是排序问题

假定在研究的排序问题中有n个工件.由于车辆的运输容量是有限的，即每次运输最多能运c个工件，在任意一个可行排序中，最少需要k*=「n/c⎤个运输批.而一个运输批被称为满的，是指这个运输批中恰好运送了c个工件.否则，我们称一个运输批为非满的.很容易可以得到以下这个引理.

引理4(1).δ(Bi)≥αT，对1≤i≤k.

(2). 如果车辆在紧挨着时刻δ(Bi)之前是空闲的，那么有δ(Bi)=ρ(Bi).

证明：(1).由算法Dc运输阶段(步骤 1)的执行规则，显然有δ(Bi)≥αT，对1≤i≤k.

(2).已知在任意一个可行的排序中始终有δ(Bi)≥ρ(Bi).因为车辆在紧挨着时刻δ(Bi)之前是空闲的，有δ(Bi-1)+T<δ(Bi)，说明在δ(Bi)时刻之前运输批Bi中还有没有完工的工件，因而有δ(Bi)=ρ(Bi).

现在我们来分析算法Dc的竞争比为2.

由引理5和引理6，可以得到下面的定理.

定理2对于排序问题是

算法Dc是一个竞争比为2的在线算法.

4结论

研究了工件具有退化效应且有一台容量有限制的车辆参与运输的在线排序问题.用对手法找到一个坏例子来说明了任意一个在线算法它的竞争比不会小于1+α.然后设计了一个竞争比为2的在线算法.对于该问题的下界是否能够增大，又或者能否找到竞争比小于2的在线算法是进一步的研究课题.

参考文献：

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

[2]BROWNE S, YECHIALI U. Scheduling deteriorating jobs on a single processor [J]. Operations Research, 1990, 38(3): 495-498.

[3]MOSHEIOV G. Scheduling jobs under simple linear deteriorating [J]. Computer and Operations Research, 1994, 21(6): 653-659.

[4]LIU Ming, ZHENG Fei-feng, WANG Shi-jin, et al. Optimal algorithms for online single machines with deteriorating jobs [J]. Theoretical Computer Science, 2012, 445: 75-81.

[5]YU Sheng, PRODENCE W.H.WONG. Online scheduling of simple linear deteriorating jobs to minimize the total general completion time [J]. Theoretical Computer Science, 2013, 487: 95-102

[6]HOOGEVEEN J A, VESTJEN A P A. A best possible Deterministic online algorithm for minimizing maximum delivery time on a single machine [J]. SIAM Journal on Discrete Mathematics, 2000, 13(1): 56-63.

[7]FANG Yang, LU Xi-wen, LIU Pei-hai. Online batch scheduling on parallel machines with delivery times [J]. Theoretical Computer Science, 2011, 412(39): 5333-5339.

[8]NG C T, LU Ling-fa. On-line integrated production and outbound distribution scheduling to minimize the maximum delivery completion time [J]. Journal of Scheduling, 2012, 15(3): 391-398.

[9]IGOR A, MEHMET B. Semi-online two-level supply chain scheduling problems [J]. Journal of Scheduling, 2012, 15(3): 381-390.

Research on Online Scheduling with Deteriorating Jobs and Delivery Times

LIU Qi-jia1, ZHANG Li-qi2, FENG Qi3

(1.School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China; 2.College of Information and Management Science, Henan Agricultural University, Zhengzhou 450003, China; 3.College of Science, Zhongyuan University of Technology, Zhengzhou 450007, China)

Abstract:In this paper, we study the online scheduling on a single machine with deteriorating jobs and delivery times. The objective function is to minimize the maximum delivery completion time of these jobs. For this online scheduling problem, the objective is to design an effective online algorithm. We establish a lower bound by adversary strategy, i.e., design a bad instance to make the ratio of the objective by online algorithm and offiine objective as big as possible, then we present an online algorithm by this lower bound. Thus we get a lower bound by adversary strategy and an online algorithm with the competitive ratio of 2.

Key words:scheduling; deteriorating jobs; delivery

中图分类号：O223

文献标志码：A

doi:10.3969/j.issn.1671-6833.2015.02.027

文章编号:1671-6833(2015)02-0125-04

作者简介:刘其佳(1987-)，女，河南尉氏人，郑州大学博士生，主要研究方向:图论与组合最优化，E-mail:liuqijia39@163.com.

基金项目:国家自然科学基金资助项目(11401604; 11401605); 河南省基础与前沿技术研究计划资助(132300410392)

收稿日期:2014-08-30；

修订日期：2014-11-25