Philippe Chrétienne

On scheduling with the non-idling constraint *

In this paper, we give an overview of the main results obtained on the complexity of scheduling under the non-idling constraint, i.e, when the jobs assigned to each machine must be processed with no intermediate delay. That constraint is met in practice when the cost of intermediate idle time is too high due to the idle time itself and/or the machine restarting. The non idling constraint is a strong constraint that often needs a new solving approach and most results about classical scheduling problems do not easily extend to the non-idling variant of the problem. In this survey, we mainly consider the non-idling variants of the basic scheduling problems. So, we first present basic properties, complexity results and some algorithms concerning the one-machine non-idling scheduling problem. Then we consider the m-machine non idling scheduling problem. We show that a few basic problems may be solved by rather easy extensions of the algorithm solving their classical counterpart. However, the complexity status of the non idling version of quite easy polynomial basic problems remains an open question. We finally consider a more constrained version of non-idling, called the "homogeneously non idling" constraint, where for any subset of machines, the union of their busy intervals must make an interval and we present the structural property that leads to a polynomial algorithm for unit time jobs and a weak precedence. We conclude by giving some research directions that seem quite interesting to study both for theoretical and practical issues.

Introduction

This paper is an updated version of [START_REF] Chrétienne | On scheduling with the non-idling constraint[END_REF]. We consider scheduling problems where a set of jobs {J 1 , • • • , J n } must be processed on a set {M 1 , • • • , M m } job J i are r i and p i . Indeed, a schedule must be such that, when the vehicle arrives at any warehouse W i , product P i must be already there. So, when arriving at warehouse W i , the vehicle must immediately load P i and then restart to W i+1 . In other words, we search for a non idling schedule. As will be shown in the paper, this problem is simple since it consists in finding a starting time of the sequence (T 1 , • • • , T n ) such that these tasks may be scheduled without any intermediate idling time. In this example, the total travel time of any schedule is n i=1 p i and no objective function has been mentionned. One could be the makespan (this problem is simple and solved in the paper). Another (much more difficult to handle in the general case) could be n i=1 f i (C i ) where C i is the completion time of task T i and where f i (t) is a cost function attached to the completion time of task T i . Problems concerning power management policies may also yield similar scheduling problems [START_REF] Irani | Algorithmic Problems in Power Management[END_REF] where for example each idling period has a cost and the total cost has to be minimized [START_REF] Baptiste | Scheduling Unit Tasks to Minimize the Number of Idle Periods: a Polynomial Time Algorithm for Off-line Dynamic Power Management[END_REF]. Note that the non-idling constraint will not necessarily ensure full machine utilization (i.e: no idling period from time 0 to the completion time of the last job of the machine) but will remove the cost of machine re-starts, maybe at the price of processing the first job of each machine later.

Contrary to the well-known no-wait constraint in shop scheduling where no idle time is allowed between the successive operations of a same job, the non-idling machine constraint has just begun to receive research attention in the literature. To the best of our knowledge, the first work on such problems concerns the earliness-tardiness single-machine scheduling problem with no unforced idle time, where a Branch and Bound approach has been developed [START_REF] Valente | An Exact Approach to Early/Tardy Scheduling with Releases Dates[END_REF]. More recently, some aspects of the impact of the non-idling constraint on the complexity of single-machine scheduling problems as well as the important role played by the earliest starting time of a non-idling schedule has been studied in [START_REF] Chrétienne | On single-machine scheduling without intermediate delays[END_REF]. Moreover, in [START_REF] Jouglet | Single-machine scheduling with no idle time and release dates to minimize a regular criterion[END_REF] and [START_REF] Carlier | Exact resolution of the nemachine sequencing problem with no machine idle time[END_REF], exact methods have been designed to solve the basic one-machine non-idling problem and in [START_REF] Kacem | Approximation algorithms for no idle time scheduling on a single machine with release times and delivery times[END_REF], approximation algorithms have been developped for the non-idling single-machine scheduling problem with release and delivery times.

The non-idling single-machine problem

Let Π = 1|r j , prec|Φ be a one-machine scheduling problem with jobs set J = {J 1 , • • • , J n } where:

• the release dates r j are compatible with prec (i.e: if job J i precedes job J j , then r j ≥ r i + p i ) and satisfy r 1 ≤ • • • ≤r n ;

• Φ is a regular objective function;

• all numerical data are positive integers.

For any K ⊂ {1, • • • , n}, the sum j∈K p j is denoted by P K . Let σ = (J i 1 , • • • , J in ). The sequence σ is said to be feasible if there is at least one feasible schedule with sequence σ. If σ is feasible, we denote by e(σ) the earliest feasible schedule with sequence σ. Since Φ is regular, e(σ) is also the best feasible schedule with sequence σ. Finally we denote by Σ the set of the feasible sequences and by Σ * the subset of the optimal sequences of Σ.

The non-idling scheduling problem Π N I associated with Π is denoted by 1, N I|r j , prec|Φ in the 3-field notation. Π N I has exactly the same instances as Π but, for each instance, the candidate schedules are those feasible schedules whose jobs are processed on the machine with no intermediate delay.

In the non preemptive case, a sequence σ = (J i 1 , • • • , J in ) is said to be NIfeasible if there is at least one non-idling feasible schedule with sequence σ. Given a NI-feasible sequence σ, we denote by e N I (σ) the earliest non-idling feasible schedule with sequence σ. Since Φ is regular, e N I (σ) is also the best non-idling feasible schedule with sequence σ.

It is easily seen that the starting time α N I (σ) of e N I (σ) is as follows:

α N I (σ) = max{0, max k∈{1,••• ,n} {r i k - k-1 q=1 p iq }
Moreover, as illustrated in Figure 1, we got in this case e N I (σ) from e(σ) simply by right-shifting all the blocks of e(σ) except the last one. Finally, α N I and β N I will respectively denote the earliest starting time of a non-idling feasible schedule and the earliest starting time of an optimal non-idling feasible schedule, whenever these schedules exist.

Complexity aspects

Let us first observe that 1, N I|r j , d j |-is NP-complete in the strong sense since in the well-known reduction from 3-PARTITION, the feasible schedules of the instance of 1|r j , d j |-are non-idling [?]. The same argument may be used from [START_REF] Lenstra | Complexity of Scheduling under Precedence Constraints[END_REF] to show that the decision versions of 1, N I|r j |L max and 1, N I|r j | C j are respectively NP-complete and NPcomplete in the strong sense. Nevertheless it is not always true that the non-idling version of an NPcomplete single-machine scheduling problem is also NP-complete. For example, deciding whether non-preemptive jobs may be scheduled within given machine availability time intervals, is NP-complete while its non-idling variant is clearly polynomial.

The earliest starting time of a non-idling schedule

We know from Section 2.1 that the question whether a non-idling schedule exists is an NP-complete problem. In fact, when Π has no hard deadlines or if the time windows are regular (i.e: (i, j) ∈ prec ⇒ (r i ≤ r j ) and (d i ≤ d j )), then there is at least one non-idling schedule and α N I is easy to compute. Property 1. Assume Π = 1, N I|r j , prec|Φ either has no hard deadlines or has regular time windows and at least one NI-feasible sequence. Then

α N I = α N I (J 1 , • • • , J n ).
Proof. In both cases, we know that Σ N I = ∅. Let σ be a sequence of Σ N I such that the two consecutive jobs J i and J j satisfy i > j. Since J i is not an ascendant of J j in the precedence graph, we may exchange these two jobs in the schedule e N I (σ) and get a feasible non-idling schedule starting at time α N I (σ) and whose sequence σ is obtained by exchanging the jobs J i and J j in σ. Since e N I (σ ) is the earliest non-idling schedule with sequence σ , we get that α N I (σ ) ≤ α N I (σ). After O(n 2 ) such exchanges, we get that

(J 1 , • • • , J n )) is a N I-feasible sequence and that α N I ((J 1 , • • • , J n )) ≤ α N I (σ).
Remark 1. When Π has no hard deadlines, α N I may be computed in polynomial time. So any problem 1, N I|prec, r i |f (C max ), where f is non-decreasing, is polynomial. In that case the non-idling schedule e N I (J 1 , • • • , J n ) is optimal.

Some specificities of non-idling scheduling

Let Π be a single-machine scheduling problem such that Σ N I = ∅. Figure 2 illustrates a situation where β N I > α N I for a small instance with 2 jobs and the cost function

C 1 + 3C 2 . schedule e(J 1 ,J 2
) : cost=11 optimal non-idling schedule : cost=10

J 1 J 2 0 1 2 r 1 r 2 3 J 1 J 2 0 1 2 r 1 r 2 4 Figure 2: β N I > α N I
We now give an example showing that a sequence of Σ * may not be a sequence of Σ * N I . Consider the instance of 1, N I|r j , p j , q j | max(C j + q j ) where q j is the tail of job J j and whose data are given in the array below: i 1 2 3 4 5 6 p i 5 3 4 3 5 3 r i 0 10 11 11 20 30 q i 40 7 26 24 31 8 Figure 3 shows first the schedule of Σ we get using the Jackson's rule. This schedule is optimal since its cost is 56 and in any schedule we have C 5 + q 5 ≥ 56. So the sequence π = (J 1 , J 2 , J 3 , J 4 , J 5 , J 6 ) is in Σ * . The next schedule is e N I (π) whose cost is 61 and where it clearly appears that scheduling job J 2 at time 15 is not a good decision since jobs J 3 and J 4 are also ready at that time but have greater latency times. The last schedule is e N I (J 1 , J 3 , J 5 , J 4 , J 2 , J 6 ), which is an optimal non-idling schedule since its cost is 56. Before introducing a third example, let us denote by I(u) (u ≥ 0) the instance of Π with the same parameter values as the initial instance (say I) except for the release dates r j (u) which are defined by: ∀j ∈ {1, • • • , n}, r j (u) = max{r j , l j + u} where l j is the value of longest path ending at J j in the precedence graph of I. The feasible schedules of I(u) are the schedules of I whose starting time is e(σ,u) and e N I (σ, u) are defined in the same way as Σ, Σ N I , Σ * , Σ * N I , α(σ), α N I (σ), e(σ) and e N I (σ) for instance I but apply to the instance I(u). What the following example shows is that if u -is the smallest u such that there is a sequence σ in Σ * (u -) such that the schedule e(σ, u -) is non-idling, then this schedule is not necessarily an optimal non-idling schedule. Let us consider the instance described by the following array where the objective function is For this instance, we thus have u -= 5 but the corresponding non-idling schedule e((a, c, b), 5) of Σ * (5) is not an optimal non-idling schedule since the schedule e N I ((a, b, c)) has cost 5.

f a (C a ) + f b (C b ) + f c (C c ). jobs p j r j f j (t) a 2 0 { 0 if 2 ≤ t ≤ 5, t -5 otherwise. b 3 5 t -8 c 2 7 5(t -9)

The Earliest Non-Idling property

The question whether there is an optimal non-idling schedule starting at time α N I is clearly a quite interesting matter. . A problem with that property is said to have the ENI property. In [START_REF] Chrétienne | On single-machine scheduling without intermediate delays[END_REF], "No-Wait" schedules (in short NW schedules) are introduced and it is proved that problems for which NW schedules are dominant have the ENI property. Moreover it is shown that preemptive problems have the ENI property.

Definition 1. A schedule is said to be no-wait if it is non-idling whenever there is at least one non completed available job.

Property 2. If the NW schedules are dominant, then Π has the ENI property.

Remark 2. The dominance of NW schedules is not a necessary condition for the ENI property to be satisfied. This is illustrated by the small example of Figure 2 with two jobs where e(J 1 , J 2 ) is the unique NW schedule of Σ while the optimal non-idling schedule, which starts at time

β N I = α N I = r 2 , is e(J 2 , J 1
).

An interesting case when the ENI property is satisfied is when preemption is allowed. The formal proof, given in [START_REF] Chrétienne | On single-machine scheduling without intermediate delays[END_REF], shows that, in this case, NW-schedules are dominant. Property 3. If preemption is allowed, then the ENI property is satisfied.

Property 3 may be used to easily solve problems 1, N I|prec, r j , pmtn|f max , 1, N I|r j , pmtn| C j and 1, N I|r j , d j , pmtn|-. In each case, the algorithm first computes α N I and then applies the algorithm solving the unrestricted problem to the instance I(α N I ). Consider for example the instance of 1, N I|r j , d j , pmtn|-whose data are written in the array below: j 0 1 2 3 4 5 6 7 8 p j 3 4 2 5 7 2 1 2 2 r j 0 0 4 13 16 27 28 32 32 d j 23 24 23 27 23 32 30 36 38

We have α N I = 8. Applying the Jackson preemptive algorithm to I(8), we get the non-idling schedule illustrated by Figure 6. Since this schedule is not feasible (job 3 is completed at time 29), we may conclude that the original instance has no feasible preemptive non-idling schedule.

(σ) = min k∈{1,••• ,n} { di k -P {i 1 ,••• ,i k } } is (if
N I (σ) ≤ u ≤ ω N I (σ).
It follows from the definitions of α N I (σ) and ω N I (σ) that the critical times of an instance are the distinct and non negative values we may obtain from:

1. the values r j -P K where J j is a job and K is a subset of jobs such that J j ∈ K;

2. the values d j -P K where J j is a job and K is a subset of jobs such that J j ∈ K.

Also note that if 0 is not such a value, then by convention it will also be considered as a critical time. If N is the number of critical times, then we denote by (c 1 , • • • , c N ) the sorted list of these values. Let z * (c k ), k ∈ {1, • • • , N } be an optimal non-idling schedule starting at time c k . The next property, whose proof is given in [START_REF] Chrétienne | On single-machine scheduling without intermediate delays[END_REF], shows that the schedule z * (c k ) whose cost is minimum is an optimal non-idling schedule.

* (c k * )) ≤ Φ(z * (c k )). Then z * (c k *
) is an optimal non-idling schedule.

Equal processing times

We assume in this section that Π N I is a single-machine scheduling problem whose non preemptive jobs have the same processing time p and that the objective function Φ(s) has one of the two forms f j (C j ) or max f j (C j ) where f j is a non decreasing function of the completion time of J j . We first consider the special case of independent jobs and show that the corresponding problems are polynomial even if the individual cost functions are no longer regular. It is clear from their definition that the critical times of an instance are the distinct and non negative values we may obtain from:

1. the value 0;

2. the values r j -ap where J j is a job and a ∈ {0, • • • , n -1};

3. the values d j -bp where J j is a job and b ∈ {0, • • • , n} .

We thus know that N (the number of critical times) is O(n 2 ) and that the sorted list (c 1 , • • • , c N ) of the critical times may be computed in O(n 2 log n) time. Let u ≥ 0 and let us denote by z * (u) an optimal non-idling schedule starting at u (if such a schedule exists). Property 5 shows [START_REF] Chrétienne | On single-machine scheduling without intermediate delays[END_REF] that, if it exists, the schedule z * (u) may be computed by solving an assignment problem. Property 5. For any time u ≥ 0, the schedule z * (u) may be computed in polynomial time It follows from Property 4 and Property 5 that the problems 1, N I|p j = p, r j , d j |Φ where Φ has one of the two forms f j (C j ) or max f j (C j ) are polynomial.

Let us now consider the case of dependent jobs, that is the class of problems 1, N I|r j , p j = p, prec|Φ. We get from Property 4 that a sufficient condition for the problem to be polynomial is that its special case with a fixed schedule starting time is itself polynomial. The preceding argument may for example be applied to show that problems 1, N I|r j , p j = 1, prec| f max , 1, N I|r j , p j = p, prec| C i and 1, N I|r j , p j = p, prec| L max are polynomial since their variant with a fixed schedule starting time is itself polynomial [START_REF] Baker | Preemptive Scheduling of a Single Machine to Minimize Maximum Cost subject to Release Dates and Precedence Constraints[END_REF], [START_REF] Brucker | Scheduling Algorithms[END_REF].

The non-idling m-machine problem

We consider in this section the case when m identical parallel machines are available to process the jobs and when the jobs assigned to each machine must be processed without any intermediate delay. We first consider the special case with fixed job sequences on each machine. Then we show that the problems P, N I|p j = 1, intree| C max , P 2, N I|p j = 1, prec| C max and P 2, N I|p j = 1, r j , d j |-may be solved by rather easy extensions of the algorithms solving their classical versions. We then show that the problem P, N I|p j = 1, prec| C max is NP-hard while the complexity of P, N I|p j = 1, r j , d j |-is still unknown. We finally consider a stronger version of the non-idling constraint, called the Homogeneously Non-Idling constraint (HNI in short), where, for every subset of machines, the union of their busy periods must be an interval. For the special case P, HN I|p j = 1, r j , d j |-, we provide a necessary and sufficient condition for a schedule to exist and we propose a polynomial algorithm to solve the problem.

Fixed sequences of jobs on each machine

Let us denote by L k the sequence of jobs processed by machine M k , by L k (p) the job with rank p in L k and assume that L k is compatible with prec (i.e., J i = L k (r), J j = L k (s) and (J i , J j ) ∈ prec implies r < s). Then a schedule is entirely defined by the starting times θ k of the first job of each sequence. If (J i , J j ) ∈ prec, J i = L k (q), J j = L l (r) and k = l, then the precedence constraint (J i , J j ) is satisfied if and only if:

θ l + P l (r -1) ≥ θ k + P k (q)
where P k (r) = r s=1 p L k (s) . Now, if we consider all the precedence constraints (J i , J j ) such that J i is in L k and J j is in L l , all these constraints will be satisfied if and only if :

θ l -θ k ≥ max{P k (q) -P l (r -1)|(J i , J j ) ∈ prec} = v(k, l, prec).
Let us define the arc-valued graph GM = (M, A) where M is the set of machines, and where there is an arc (M k , M l ) valued by v(k, l, prec) if there is at least one precedence constraint (J i , J j ) in prec with J i in L k and J j in L l . Then it is clear that at least one schedule exists if and only if GM has no positive circuit and that in this case, there is an earliest schedule (i.e., the smallest θ k values) given by the values of the longest paths ending at each node of GM . Figure 7 shows the graph GM associated with two instances of the problem, one with no feasible schedule and one with an earliest schedule. An optimal NI-schedule

Extension of classic algorithms

In this section, we show that the well-known polynomial algorithms solving respectively the problems P, N I|p j = 1, intree| C max , P 2, N I|p j = 1, prec| C max and P 2, N I|p j = 1, r j , d j |-may be rather easily extended to solve their non-idling versions.

P, N I|p

j = 1, intree| C max
It is well-known that the problem P |p j = 1, intree| C max is polynomially solved by the Hu's algorithm [START_REF] Hu | Parallel sequencing and assemble line problems[END_REF], which is a list algorithm where the priority of a job is its level in the intree. A key property of the schedule issued from that list is that the number of jobs scheduled in time slot t + 1 is not more than that of time slot t. Since the machines are identical, by assigning the n(t) jobs of slot t to the machines M 1 , • • • , M n(t) , we get a non-idling schedule which is obviously optimal. Figure 8 shows an example. We recall that the problem P 2|p j = 1, prec| C max is polynomially solved by the Coffman-Graham algorithm [START_REF] Coffman | Optimal scheduling for two processor systems[END_REF] (CG algorithm in short).

Let I be an instance of P 2, N I|p j = 1, prec| C max . The following property shows that, if I has at least one schedule, then there is an optimal one with a quite specific structure.

Property 6. If I has at least one schedule, then there exists an optimal schedule whose structure is illustrated in Figure 9 where:

1. the jobs scheduled before a (called the left jobs) are the ascendants of job a in prec;

2. the jobs scheduled after b (called the right jobs) are the descendants of job b in prec;

3. the jobs scheduled after a and before b (called the middle jobs) are optimally scheduled without any idle time by the CG algorithm.

Proof. Let O be a schedule of I. If the jobs assigned to machine M 1 and the jobs assigned to machine M 2 are processed in disjoint intervals in S (case 1 of Figure 9), then by applying the corresponding transformation, we get an at least as good schedule O 1 , with no middle jobs), which has the expected structure. If the two intervals contain at least a common slot (case 2 of Figure 9), then by applying the corresponding transformation, we again get an at least as good schedule O 1 (with at least two middle jobs) which has the expected structure. We now show that if the job a exists in O 1 , then O 1 may be transformed into a schedule O 2 (with the same structure) such that the jobs scheduled before the middle jobs of O 2 are the ascendants of the job a of O 2 (if there is one) in prec. Assume job J x is not an ascendant of the job a of O 1 in prec and is the last such job to be scheduled before a in O 1 . Thus, job J x may be scheduled on machine M 2 in the same time slot as job a and all the jobs scheduled in O 1 after J x may be left-shifted by one time slot (see Figure 10). Iterating the process until either the job a (of the current schedule) no longer exists or all jobs scheduled before a are the ascendants of a, we get a schedule O 2 at least as good as O 1 satisfying the condition 1) of the property.

The same line of reasoning may be applied to the schedule O 2 if there is a job b in that schedule.

We thus finally get a schedule O 3 at least as good as O 2 satisfying the conditions 1) and 2) of the property. If O 3 has some middle jobs, it is clear that, since the partial schedule of O 3 restricted to these middle jobs has no idle time, the condition 3) of the property is also satisfied by O 3 .

a b

The structure of a dominant NI-schedule

P 2, N I|p

j = 1, r j , d j |-
We recall that the problem P 2, N I|p j = 1, r j , d j |-is polynomially solved by the Earliest Deadline First algorithm (EDF algorithm in short) that schedules one ready job with the minimum deadline as soon as a machine is idle and there is at least one ready job. Let I be an instance of P 2, N I|p j = 1, r j , d j |-. The following property shows that, if I has at least a schedule, then there is an optimal one with the following structure.

Property 7. If I has at least one schedule, then there exists an optimal schedule such that the value of the starting time of the busy period of each machine is r j -k where j ∈ {1, • • • , n} and k ∈ {0, • • • , n}.

Proof. Assume that I has a schedule that executes respectively the sequences σ 1 and σ 2 on M 1 and M 2 . Let n 1 = |σ 1 | and n 2 = |σ 2 |. We know from Section 2 that e N I (σ 1 ) and e N I (σ 2 ) are also feasible non-idling schedules of the corresponding subsets of jobs. Since

α N I (σ 1 ) = max{0, max k∈{1,••• ,n 1 } {r i k - (k-1)} and α N I (σ 2 ) = max{0, max k∈{1,••• ,n 2 } {r i k -(k-1
)}, we get a feasible non-idling schedule with the required structure.

Let us now consider the following variant, NI-EDF, of EDF that takes as input the instance I, the starting time slots a 1 , a 2 (with values satisfying Property 7) of the busy periods of M 1 and M 2 and the numbers of jobs n 1 and n 2 . Let a = min{a 1 , a 2 } and b = max{a 1 , a 2 }. The NI-EDF applies the following rule at each time-slot t from the leftmost one. If t belongs to exactly one of the two busy periods and there is at least one unscheduled ready job, then schedule one ready job with the minimum deadline and consider the next time slot. If there is no ready unscheduled job at t, then stop (failure case). If t belongs to the two busy periods and there are at least two unscheduled ready jobs, then schedule the jobs with the two smallest deadlines and consider the next time slot. If there is at most one ready unscheduled job at t, then stop (failure case). It is easy to show that the instance I has at least a schedule where the busy periods of machines M 1 and M 2 are respectively the sets of time slots {a 1 , • • • , a 1 +n 1 -1} and {a 2 , • • • , a 2 +n 2 -1} if and only if the the algorithm NI-EDF applied to (I, a 1 , a 2 , n 1 , n 2 ) does not stop in the failure case. Since NI-EDF is clearly polynomial, we get from Property 7 that the problem P 2, N I|p j = 1, r j , d j |-is polynomial. It is easy to see that this result easily extends to a fixed number k of machines, that is P k, N I|p j = 1, r j , d j |-is polynomial.

The homogeneous non-idling constraint

Up to now, the complexity of P, N I|p j = 1, r j , d j |-remains an open question. So, in order to better understand why the complexity analysis of this problem is difficult, a more constrained variant of P, N I|p j = 1, r j , d j |has been studied [START_REF] Quilliot | Homogeneously non-idling schedules of unit-time jobs on identical parallel machine[END_REF] where the non-idling constraint is replaced by the homogeneously non idling (HNI in short) constraint. A schedule satisfies the HNI constraint if, for any subset M of machines, the time slots at which at least one of the machines of M is busy, make an interval. Clearly an HNI schedule is an NI schedule but the converse is not true, as shown on Figure 11 where the schedule on the left does not satisfy the HNI constraint since, for the subset {M 1 , M 3 }, the set of the times units when M 1 or M 3 is busy, is not an interval. On the contrary, the schedule on the right is an HNI-schedule. So, we are given a set J = {J 1 , • • • , J n } of n unit-time independent jobs that are to be processed on a set M = {M 1 , • • • , M m } of m identical machines. Job J i must be executed within a given time-window

F (i) = {r i , • • • , d i }.
A schedule (T, µ) assigns a time-unit T (i) and a machine µ(i) to each job J i so that :

1. for each job J i ∈ J, T (i) ∈ F (i); 2. for each time slot t, |{i|T (i) = t}| ≤ m; 3. for any M ⊆ M , the time units t at which there is at least a job J i processed at t (i.e: T (i) = t) by a machine of M ((i.e: µ(i) ∈ M ) make a single interval. The decision problem Π 0 is to decide whether a given instance (J, F, m) has at least one schedule. If the answer is yes, the instance is said to be feasible.

Assume that (T, µ) is a schedule of the instance (J, F, m) and let us denote by n T (t) the number of jobs scheduled in the time slot t. It is easy to see that if the n T (t) jobs scheduled in time slot t are assigned to the machines M 1 , • • • , M n T (t) , then we get a new schedule with the so called pyramidal structure as shown on Figure 12. Thus an m-matching T , which is not a schedule, has at least a k-hole (k ∈ {0, • • • , m -1}), i.e., a time slot t such that there are two time slots t and t with t < t < t , n T (t ) > k, n T (t ) > k and n T (t) = k. As an example, time slot t = 2 is a 1-hole of the m-matching on the left part of Figure 12. , where Int(Θ) is the set of the intervals contained in Θ. Moreover, if Θ 1 and Θ 2 are two intervals such that Θ 1 ∪ Θ 2 is not an interval (two such intervals will be called disconnected ), then M id(Θ 1 , Θ 2 ) is the interval made by the time slots between Θ 1 and Θ 2 . Finally (Θ 1 , • • • , Θ s ) is a sequence of disconnected intervals if for i ∈ {1, • • • , s -1} the ending time slot of Θ i is strictly smaller than the starting time slot of Θ i+1 .

Existence of a schedule

Let I = (J, F, m) be an instance of Π 0 . Following are three basic properties of Π 0 , the first two ones concern the existence of an m-matching, the third one comes from the pyramidal structure of a schedule.

(J(Θ 1 ∪ J(Θ 2 ))| < |M id(Θ 1 , Θ 2 )| min{λ(Θ 1 ), λ(Θ 2 )}, then I has no schedule.
The necessary and sufficient condition for a schedule to exist is an extension of Property 10 to an arbitrary sequence (Θ 1 , • • • , Θ s ) of disconnected intervals. The following theorem has been proved in [START_REF] Quilliot | Homogeneously non-idling schedules of unit-time jobs on identical parallel machine[END_REF].

for any sequence

(Θ 1 , • • • , Θ s ) of disconnected intervals, |J\∪ s i=1 J(Θ i )| ≥ s-1 i=1 |M id(Θ i , Θ i+1 | × min{λ(Θ i ), λ(Θ i+1 )}
Proving that the two conditions are necessary is easy while proving their sufficiency is more difficult and needs to introduce the concept of a k-schedule. A k-schedule is an m-matching with a pyramidal structure up to the level k (i.e., the function min{k, n T (t)} has a pyramidal structure). Figure 13 illustrates this definition.

Then, the following theorem is proved using induction on k: Let us first present the concept of propagation path, which will be the basic tool used by the algorithm. The propagation graph G(T ) = (H, E(T )) is the directed graph such that (t, t ) ∈ E(T ) if t = t and there is at least one job J i scheduled at t such that t ∈ F (i). If job J i is scheduled at t and if t ∈ F (i), then J i is said to be a label of the arc (t, t ). A propagation path of T is an elementary path γ = (t 0 , • • • , t k ) of G(T ). A propagation path is labelled when all its arcs are assigned a label and is said to be fitted if it is labelled and satisfies n T (t k ) < m.

for any sequence

(Θ 1 , • • • , Θ s ) of disconnected intervals, |J\∪ s i=1 J(Θ i )| ≥ s-1 i=1 |M id(Θ i , Θ i+1 | × min{k, λ(Θ i ), λ(Θ i+1 )}
If γ = (t 0 , • • • , t k ) is a propagation path of G(T ) fitted with the la- belling σ = (J [0] , • • • , J [k-1]
), we get another m-matching T = T (T, γ, σ) by putting T (J [p] ) = t p+1 for all p ∈ {0, • • • , k -1}. Figure 14 illustrates this transformation.

k-schedules, as defined in the preceding section, are again essential in the derivation of the algorithm. Note first that a 0-schedule always exists and that an m-schedule is a schedule. The algorithm QuickSearchSchedule-(J, F, m) presented below works as follows. It first checks for an m-matching T of I. If there is no m-matching, then it stops in the failure case. Otherwise it searches for the greatest k 0 such that T is a k 0 -schedule and sets the variable k to k 0 . Then it searches iteratively for a propagation path to transform the current k-schedule into a new one either with strictly less k-holes or with a more flat structure. If the current k-schedule is such that there is no propagation path that removes a k-hole or makes the structure more flat, then a sequence of disconnected intervals that does not satisfy Condition 2 of Theorem 2 may be found from the current k-schedule. So, in that case, we know that the instance I has no (k + 1)-schedule. Otherwise, (5) while k < m and not stop do [START_REF] Landis | Group Technology and Cellular Manufacturing in the Westvaco Los Angeles VH Department[END_REF] while not (H = ∅) and not stop do [START_REF] Irani | Algorithmic Problems in Power Management[END_REF] if there is a path γ from u ∈ Ŝ to v ∈ H then [trans(T, γ);break] (9)

if there is a path γ from u ∈ ∪ k+1 p=1 {C + p , C - p } to v ∈ H then [trans(T, γ);break] [START_REF] Baker | Preemptive Scheduling of a Single Machine to Minimize Maximum Cost subject to Release Dates and Precedence Constraints[END_REF] if there is a path γ from u ∈ Ŝ to v ∈ {C + k+1 + 1, C - k+1 -1} then [trans(T, γ);break] (13) if there is a path of G(T ) from u to v where: procedure trans(T, γ);

(1) Let σ be a label of γ;

(2) T ← T (T, γ, σ).

It is worth noting that the propagation path chosen at each iteration of the inner loop (line 19) is not an arbitrary one satisfying the required starting and end node. If this choice was left free, then the algorithm would not be polynomial. On the contrary, if at each iteration, we choose the propagation path with a maximum level difference between its starting and ending nodes, it can be shown (bit this is not that easy) that the number of iterations for a given value of k is polynomial [START_REF] Quilliot | A polynomial algorithm for the homogeneously non-idling scheduling problem of unit-time independent jobs on identical parallel machine[END_REF].

Conclusion

In this paper, we have proposed a survey on the specific type of scheduling problems where intermediate delays between jobs executed by the same machine are not allowed. Even if such problems are encountered in practice, they have been investigated rather recently. In this context, the paper presents results about the non-idling variants of very basic scheduling problems. These results have been established mainly from the complexity point of view and it is clear that, in each case, more efficient algorithms could be developed. Quite many research directions are still to be investigated. From a theoretical point of view, it seems for example important to classify the problem P, N I|p i = 1, r i , d i |-and answer the following question: does a polynomial single-machine classical scheduling problem with a regular objective have a polynomial counterpart? If the restriction to a regular objective function is removed, we know the answer is no. Another important direction for which very few and often negative results are known, concerns approximation algorithms for non-idling problems. Practical applications also ask for studying scheduling problems with two sets of resources, one set for which the tasks assigned to the resource must be processed in the non-idling mode and one set for which they are processed in the classical mode.

Figure 1 :

 1 Figure 1: From e(σ) to e N I (σ)

Figure 3 :

 3 Figure 3: An instance such that S * ∩ S * N I = ∅

Figure 4

 4 Figure 4 first shows the schedules e(σ, u) for the six orders and for the three cases: u = 3, 3 < u < 5 and u = 5. In each rectangle of a schedule are inscribed the job and its individual cost in the schedule. First, it is easy to see that α N I = 3. We see that Σ * (3) = {(a, c, b)} and that the corresponding schedule e((a, c, b), 3) has cost 4 but is not a nonidling schedule. For 3 < u < 5, we still have Σ * (u) = {(a, c, b)} and the corresponding schedule e((a, c, b), u) whose cost is u + 1 is not a non-idling schedule. At time u = 5, we again have Σ * (5) = {(a, c, b)} but now the corresponding schedule e((a, c, b), 5) is a non-idling schedule with cost 6. For this instance, we thus have u -= 5 but the corresponding non-idling schedule e((a, c, b), 5) of Σ * (5) is not an optimal non-idling schedule since the schedule e N I ((a, b, c)) has cost 5.

Figure 4 :Figure 5 :

 45 Figure 4: (a, c, b) ∈ Σ * (5),e((a, c, b), 5) is non-idling but not optimal

Figure 6 :

 6 Figure 6: An optimal non-idling schedule

Property 4 .

 4 Let (c 1 , • • • , c N ) be the sorted list of the critical times of an instance of Π N I and let k * be such that: ∀k, Φ(z

Figure 7 :

 7 Figure 7: 2 instances with fixed sequences of jobs.

Figure 8 :

 8 Figure 8: an instance of P, N I|p j = 1, intree| C max .

Figure 9 : 2 Figure 10 :

 9210 Figure 9: The dominant structure of NI-schedules.

Figure 11 :

 11 Figure 11: HNI-schedule versus non-HNI schedule

Figure 12 :

 12 Figure 12: The pyramidal structure

Property 8 .

 8 For any interval Θ and any m-matching T of I, there is at least one time slot t of Θ such that n T (t) ≥ λ(Θ) Property 9. I has at least one m-matching if and only if, for any interval Θ, we have |J(Θ)| ≤ m|Θ| Property 10. Let Θ 1 and Θ 2 be two disconnected intervals. If |J \

Theorem 1 .

 1 I = (J, F, m) has at least one schedule if and only if 1. for any interval Θ, |J(Θ)| ≤ |Θ| × m;

Theorem 2 .

 2 I = (J, F, m) has at least one k-schedule if and only if 1. for any interval Θ, |J(Θ)| ≤ |Θ| × m;

Figure 13 :

 13 Figure 13: k-schedule

Figure 14 :

 14 Figure 14: The new m-matching T = T (T, γ, σ)

( 14 )

 14 u = C + p ,v = C + p-1 + 1 and C + p < C + p-1 for some p ∈ {2, • • • , k + 1} (15) or u = C + p ,v = C + p + 1 and C + p = C + p-1 for some p ∈ {2, • • • , k + 1} (16) or u = C - p ,v = C - p-1 -1 and C - p < C - p-1 for some p ∈ {2, • • • , k + 1} (17) or u = C - p ,v = C - p -1 and C - p = C - p-1 for some p ∈ {2, • • • , k + 1} (18) then (19) choose a path γ such that n T (u) -n T (v)is maximum; (20) [trans(T, γ);break] (21) stop ← true; (22) endwhile; (23) if not (stop) then k ← k + 1; (24) endwhile; (25) if k = m then return(T ) else return(nil).