(1.School of Management Engineering,Zhengzhou University of Aeronautics,Zhengzhou 450046,China;2.School of Mathematics and Statistics,Zhengzhou University,Zhengzhou 450001,China;3.School of Sciences,Henan University of Technology,Zhengzhou 450001,China)

Abstract: We study the single-machine preemptive scheduling problem with multiple maintenance activities to minimize the total late work,in which the jobs must be processed in the time space not occupied by the maintenance intervals.For this problem,we present a polynomial algorithm to determine the optimal schedule and establish a formula expression to the optimal value.Moreover,our result is used to correct some minor errors in the literature related to the single-machine (preemptive or non-preemptive) scheduling with one maintenance activity to minimize the total late work.

Keywords: Scheduling;Late work;Maintenance intervals

§1.Introduction

In the last decades,scheduling with maintenance activities and scheduling with late work criterion are two hot topics in scheduling research.Research for the combination of the two topics is a newly developed direction in the literature.Then we consider the single-machine scheduling problems with multiple maintenance activities to minimize the total late work.Scheduling problem with maintenance activities was first introduced by Schmidt [10].In the last decades,this topic has been extensively studied.Representative work can be found in literature[3,13,14].Scheduling related to late work criterion was first studied by Blazewicz and Finke [1].Then a number of research groups focus on this performance measure,obtaining a set of interesting results.Potts and Wassenhove [8] considered problem 1||∑Yj.They showed that the problem is NP-hard and presented a pseudo-polynomial-time algorithm.For the same problem,Potts and Wassenhove [9] presented two fully polynomial-time approximation schemes (FPTASs) with running timesandrespectively.Yin et al.[12] considered problem 1,h1||∑Yj.The NP-hardness of the problem is implied in the NP-hardness of problem 1||∑Yjestablished in Potts and Wassenhove [8] for the version without maintenance activity.By showing that the problem has no polynomial-time approximation algorithm with a finite performance ratio,they study a new version of problem 1,h1||∑Yj+pmax,and presented an FPTAS.For detailed results on scheduling related to late work criterion,we refer the reader to literature [2,4–7,11,15,16].

Suppose that we havenindependent jobsJ{J1,J2,...,Jn}to be processed on a single machine with or without preemption.Each jobJj Jhas a processing timepj ＞0 and a due datedj ≥0.Letpmaxmax{pj:j1,2,...,n}be the maximum processing time of the jobs inJ.For convenience,we assume that the jobs inJare indexed in the EDD (earliest due date)order such that

As for the single machine,it can process at most one job at a time and is assumed not to be available for processing during any forbidden interval.

Given a scheduleπof the jobs inJ,we useCj(π) to denote the completion time of jobJj.In the non-preemptive version,the late work of jobJjunderπ,denoted byYj(π),is the amount of processing time ofJjafter its due datedjinπ.Sinceπis a non-preemptive schedule,we have

or equivalently,

In this paper,we mainly focus on the research for the following single-machine preemptive scheduling problem with multiple maintenance activities

where “1,hm” in theα-field imples that we havemforbidden intervalsi1,2,...,m,which are mutually disjoint and are occupied bymmaintenance activities,respectively.In the case wherem1,we just write[T1,T2].The research in [7] implies that the problem,which is more general than the problem in (1.3),is polynomially solvable.But we study the problem in (1.3) by an approach different from that in [7].

For the problem in(1.3),we provide a polynomial algorithm,denoted by PSA′,with running timeO(nlogn+mlogm).Our result is also used to correct some minor errors in the algorithm PSA presented in [12] for problem 1,h1|pmtn|∑Yjand re-estimate the lower and upper bounds of the optimal value of problem 1,h1||∑Yj+pmaxin [12].Note that the authors of [12] adopt the following two assumptions that are used in [12]:

and

This paper is organized as follows.In Section 2,we present a polynomial algorithm PSA′for our problem and establish a formula expression to the optimal value.In Section 3,we point out the flaw of algorithm PSA in Yin et al.[12] by constructing a counterexample and then correct the minor errors,followed by some auxiliary discussions.In Section 4,we give the conclusion of this paper.

§2.Algorithm PSA′

In this section,we consider the scheduling problem 1,hm|pmtn|∑Yj.We will provide an algorithm,called PSA′,to solve this problem.

For each index+1,...,n},the completion time ofinσis given by

However, she did not even hint to the Princess that Featherhead was anything but absolutely perfect, and talked of him so much that when at last she announced that he was coming to visit her, Celandine made up her mind that this delightful Prince would be certain to fall in love with her at once, and was quite pleased at the idea

·For each1,2,...,m+1},we set

as required in (2.13).

Proof.Correctness of the algorithm follows from Theorems 2.1 and 2.2.Then we consider the computational complexity of the algorithm.

The preprocessing procedure runs inO(nlogn+mlogm) time.From Lemma 2.1,Step 1 runs inO(n+m) time.Moreover,each of the other steps runs inO(n+m) time.Thus,the overall time complexity of algorithm PSA′isO(nlogn+mlogm).

§3.Algorithm PSA and its flaw

In this section,we show that the algorithm presented in Yin et al.[12] for problem 1,h1|pmtn|∑Yjhas a minor flaw by constructing a counterexample.The algorithm PSA for solving problem 1,h1|pmtn|∑Yjin [12] can be roughly stated as follows.

First,the jobs are preemptively scheduled from time 0 in the earliest due date first (EDD)order(J1,J2,...,Jn)subject to the maintenance activity[T1,T2],and then the algorithm calculates the value Tmaxwhich is the maximum tardiness of the jobs in the schedule.If Tmax0,then the preemptive EDD schedule is an optimal schedule.If Tmax＞0,a new preemptive schedule is constructed by repositioning the first Tmaxunits of processing at the end of the schedule and by preemptively rescheduling the jobs in the new ordering from time 0.If∑pj-Tmax≤T1,then the starting time of the repositioning job J1is T2.Otherwise,the starting time of the repositioning job J1is the completion time of Jn.

Then,Yin et al.[12] presented the following theorem for their algorithm PSA.

Theorem 5.1:Algorithm PSA solves problem1,h1|pmtn|∑Yj,yielding the optimal objective value Tmax,in time O(nlogn).

But a flaw appears in the proof of their Theorem 5.1 in [12]:The proof that Tmaxis the optimal objective value of problem1,h1|pmtn|∑Yj is analogous to that of Theorem 1 in Potts and Van Wassenhove [8].In fact,the interference from the maintenance activity [T1,T2] makes it impossible for us to apply the method in [8] directly.Let us consider the following example.

Fig.2 Schedule σ.

A Counterexample:Letn3,p1p320,p210,d120,d2d330,T130 andT240.

For the above instance,as displayed in Figure 1,the preemptive EDD schedule is given byπ(J1,J2,h1,J3),which is in coincidence non-preemptive.SinceJ1andJ2are early andJ3is late inπ,it is easy to verify thatTmax(π)30 and ∑Yj(π)20.This further implies thatZ*≤∑Yj(π)+pmax40.By implementing the algorithm PSA in[12],we obtain a scheduleσ(J3,h1,J1,J2) with ∑Yj(σ)Tmax(π)30,as displayed in Figure 2.Since ∑Yj(π)＜∑Yj(σ),σis certainly not an optimal schedule of problem 1,h1|pmtn|∑Yj.Consequently,the algorithm PSA and Theorem 5.1 in [12] are invalid.For this instance,we also haveZ*≤40＜50Tmax(π)+pmax.Thus,the inequality in Theorem 5.2 in [12],i.e.,Tmax+pmax≤Z*,is also invalid.See Figures 1 and 2.

Note that the problem 1,h1|pmtn|∑Yjinvestigated by Yin et al.[12],which is a special case of problem 1,hm|pmtn|∑Yj,can be solved optimally by algorithm PSA′inO(nlogn) time.By usingZ′to denote the optimal value of problem 1,h1|pmtn|∑YjandZ*to denote the optimal value of problem 1,h1||∑Yj+pmax,the lower and upper bounds ofZ*in their Theorem 5.2 are replaced by

Theorem 3.1.Z′+pmax≤Z*≤Z′+3pmax-1.

Proof.SinceZ′is the optimal value of problem 1,h1|pmtn|∑YjandZ*is the optimal value of problem 1,h1||∑Yj+pmax,we haveZ′+pmax≤Z*.

Implementing algorithm PSA′,we get an optimal scheduleσ′of problem 1,h1|pmtn|∑Yj.Note thatσ′contains at most two preempted jobs.Now we obtain a scheduleσof problem 1,h1||∑Yjin the following way: Remove the preempted jobs (if any) fromσ′,keep the schedule of the non-preempted jobs inσ′unchanged,and then schedule all the preempted jobs inσ′non-preemptively at the end of the schedule.Clearly,σis a feasible schedule of problem 1,h1||∑Yjwith objective value at mostZ′+2pmax-1.Consequently,Z*≤Z′+3pmax-1.

As defined in [12],we newly defineZLZ′+pmaxandZUZ′+3pmax-1.By Theorem 3.1,we have

By embedding the relations in(3.1)in the discussion of Section 5.2 in[12],it can be observed that the FPTAS for problem 1,h1||∑Yj+pmaxis still valid without changing the time complexity.

Then we have the following theorem:

Theorem 3.2.By setting ZLZ′+pmaxand ZUZ′+3pmax-1,the algorithm DP(ZL,ZU)constructed in Yin et al.[12] is a(1+)-approximation algorithm for problem1,h1||∑Yj+pmaxand runs intime if T1≤pmaxand intime otherwise.

§4.Concluding remarks

In this paper,we study the single-machine preemptive scheduling problem with multiple maintenance activities for minimizing the total late work,i.e.,1,hm|pmtn|∑Yj.We present a polynomial algorithm for this problem with running timeO(nlogn+mlogm) and establish a formula expression to the optimal value.Moreover,we point out the flaw of algorithm PSA in Yin et al.[12] for problem 1,h1|pmtn|∑Yjby constructing a counterexample and re-estimate the lower and upper bounds of the optimal value of 1,h1||∑Yj+pmaxin [12].

For further research,we should consider the more general machine environments,such as,parallel machines,flow-shop machines,and batch machines.