New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Dominated partial schedules in time-dependent scheduling

SpeakerKrzysztof Ocetkiewicz

In this talk we will consider a single machine time-dependent scheduling problem with linear deterioration rates, i.e. the processing time is given by pi = ai+bi*si, where si is the moment a processor begins its processing the job i, ai > 0 is the base processing time and bi \ge 0 is the job deterioration rate, for i = 1, ..., n. Jobs are non-preemptive and independent, there are neither ready times nor deadlines. The goal is to minimize the total completion time. We will introduce the concept of dominated partial schedules in the 1 | pi = a+bi*si | sumCi scheduling problem. The concept will be used to increase the efficiency of a branch-and-bound search and to design another exact, but not polynomial, algorithm based on elimination of dominated partial schedules. Next, we will extend the concept to the 1 | pi = ai+bi*si | sumwiCi problem and again use it to create an exact algorithm and improve the branch-and-bound algorithm for the problem. We will present the results of computational experiments showing that the elimination of dominated partial schedules is an important step in designing efficient algorithm for the single machine time-dependent scheduling problems.