No label defined (Q4223483)

We analyze some of the standard machine scheduling models in an on-line setting. The on-line paradigm we use is that jobs arrive over time, where all job characteristics become known at their arrival. Within this paradigm we assume that the release date of a job is equal to the arrival of the job. After the introduction in chapter 1 we consider single-machine scheduling in chapter 2. The problems under consideration are the minimization of total completion time and maximum lateness with negative due dates, respectively. We give best possible deterministic on-line algorithms for both problems. Furthermore, we provide insight into the extent to which the option to restart jobs or to apply a randomized algorithm can help. In chapter 3 we consider parallel machine scheduling. The problems under consideration are the minimization of total completion time, makespan, and maximum lateness with negative due dates, respectively. As in the single-machine case, we give lower bounds on the performance guarantee for deterministic and randomized on-line algorithms, and we investigate how much restarting jobs can help. For identical machines we give a deterministic on-line algorithm with a reasonable performance guarantee for minimizing makespan. For uniform machines we give necessary and sufficient conditions on the machine speeds to allow for the existence of a deterministic on line algorithm for minimizing makespan when only a finite number of preemptions is allowed, and we also give an optimal deterministic on-line algorithm for the cases that these conditions are satisfied. In chapter 4 we consider the minimization of the makespan for the two-machine open shop, flow shop, and job shop model. Again, we provide insight in the potential benefits of randomization. In the second part of chapter 4 we consider the specific situation where a single job has to be inserted into a given schedule, without changing the order of the jobs in the schedule. We discuss the complexity of job insertion in the various shop models and give a polynomial-time heuristic for the insertion of a job in a job shop. Finally, in chapter 5, we summarize what we have learned of studying the online paradigm where jobs arrive over time. We discuss the shortcomings of competitive analysis and the used on-line paradigm, and mention some options to overcome some of these deficiencies.