scientific article; zbMATH DE number 1235242
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.
- The one machine scheduling problem: insertion of a job under the real-time constraint
- New trends in machine scheduling
- On-line scheduling of two-machine open shops where jobs arrive over time
- On-line and off-line preemptive two-machine job shop scheduling
- Single-machine online scheduling of jobs with non-delayed processing constraint
- On-line multi-threaded scheduling
- The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates
- On-line two-machine open shop scheduling with time lags
- On-line scheduling with general machine cost functions
- scientific article; zbMATH DE number 1082109 (Why is no real title available?)
- Optimal on-line algorithms for single-machine scheduling
- On-Line Scheduling In Assembly Processes
- On-line scheduling of small open shops
- A note on ``An optimal online algorithm for single machine scheduling to minimize total general completion time
- An optimal online algorithm for two-machine open shop preemptive scheduling with bounded processing times
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4223483)
