On-line Scheduling With Non-overlapping Maintenance Time On Parallel Machines

In this paper, we consider the on-line scheduling problem with non-overlapping maintenance time on parallel machines. In scheduling theory, the parallel machines scheduling is one of the most active branches. No matter whether off-line or on-line is concerned, people have been researching for decades. Most literature in parallel machines scheduling assumes that machines are available simultaneously at all times. However this availability may not be true in practice. In the real world, machines may not be available at some time due to preventive maintenance or sudden breakdown, which sometimes is called the machine availability constraints. So we have necessity to consider is situation in scheduling problems and make a reasonable decision.The non-overlapping maintenance time means that every machine M_i has a maintenance time interval [a_i, b_i), with 0≤a_i < b_i , i = 1, 2,…m, and in the set M of m parallel machines, these m maintenance time intervals either coinside or separate completely, i.e. a_i = a, b_i = b, a and b are constant, for i = 1,2,…m or a_i+1≥b_i, for i = 1, 2,…m-1. In this paper, we assume that b-a≤p_max for the former and a_i+1 -b_i≥p_max , i = 1,2,…m-1 for the latter, where p_max is the longest processing time in the job set. In above two cases, we denote by D₁ = {[a_i, b_i) | 0≤a_i < b_i, a_i= a, b_i = b, b- a≤p_max, i = 1,2,…m} and D₂ = {[a_i, b_i)| 0≤a_i < b_i, a_i+1-b_i≥p_max, i = 1,2,…m -1} respectively.On-line means that the jobs arrive by some order, and we do not know this order and the job's information in advance. A job cannot be scheduled before it arrives. The job J_j does not arrive until the job J_j-1 is scheduled. And the job J_j must be scheduled on some machine as soon as it releases and the schedule of job J_j will not be changed once it is scheduled.In this kind of scheduling problems, we consider two cases as follows. One is called r-a (resumable availability), provided that if a job cannot be finished before the unavailable period of a machine, then it can continue after the machine becomes available again. The other is called nr-a (nonresumable availability) if the job has to restart rather than continue. It is following the notation of [1].In above cases, our goal is to seek for a schedule such that the criterion makespan is minimized. In an algorithmic point of view, we want to find best possible algorithms.In this paper, we consider the cases of m =2 and m = 3, and we denote the problems byP2|on-line-list; r-a; D₁ | C_maxP2|on-line-list; nr-a; D₁ | C_max P2|on-line-list; nr-a; D₂| C_maxP3|on-line-list; nr-a; D₁| C_maxThe main results in the paper are as follows. We show an optimal on-line algorithm with worst-case ratio 2 for problem P2|on-line-list; r-a; D₁|C_max; We show that the lower bound is 2.79 and give an on-line algorithm with worst-case ratio 2.8 for problem P2|on-line-list; nr-a; D₁|C_max; We show that the lower bound is 1.99 and give an LS on-line algorithm with worst-case ratio 2 for problem P2|on-line-list; nr-a; D₂|C_max; We show that the lower bound is 3—e and give an on-line algorithm with worst-case ratio y for problem P3|on-line-list; nr-a; D₁|C_max.