| Title | : | Study of scheduling with machine availability constraints |
| Speaker | : | Sharmili N (IITM) |
| Details | : | Thu, 8 Jun, 2017 2:00 PM @ BSB 361 |
| Abstract: | : | Scheduling and its variants have real world applications. We consider a variant of scheduling where machines are not available during pre-defined time intervals during their lifetime. We specifically consider the case when non-availability intervals occur periodically and length of non-availability periods are lesser than length of availability intervals. So every machine has alternating availability and non-availability periods. There exists related work on single machine environment and 2 machine environment with makespan minimization as objective. The case studied in 2 machine environment is for parallel, identical machines, where the length of availability interval is same on both machines and length of non-availability intervals is also sam e on both machines. This may not always be the case. That is, the length of availability and non-availability periods may differ among m machines. So machines are not identical. Also machines are inherently identical, in the sense that processing time of job i is p_i on all the machines. Hence we cannot classify the machines as unrelated. We look at the machine environment which is in between identical machines and unrelated machines such that every machine has alternating availability and non-availability intervals whose length may differ among m machines and processing time of each job is same on all machines. We study this scheduling problem with 2 different objectives, namely minimizing the makespan and minimizing the sum of completion times of given set of jobs. We also consider the special case of m parallel identical machines and provide an approximation algorithm based on bin packing.
This variant of scheduling is interesting because it can be related to systems such as transportation network company, where taxi drivers are considered as machines and customers are jobs. Taxi drivers take strict periodic breaks in between which he serves costumers. The goal is to serve given customers as soon as possible, which in scheduling context corresponds to minimizing the makespan. Another example in hardware context is m processors to schedule n non-preemptive user jobs with periodic system jobs which takes up pre-defined time interval of processors such that there should not be overlap with system jobs and user jobs. We show that for the given problem with makespan minimization as objective, there does not exist a constant c approximation where c <= 2, unless P=NP. We consider the case where the machines have different availability intervals and provide a 7 approximation algorithm for the same. We also study the case when machines are identical and provide a 4 approximation algorithm. In both of these cases objective is to minimize makespan. We show that the problem with minimizing the sum of completion times with periodic non-availabilities of machines is NP hard and present an algorithm with an approximation ratio of 5. |
