On-line scheduling of jobs with fixed start and end times. (English) Zbl 0810.68068
Summary: We investigate an on-line scheduling problem on a single machine where jobs have fixed start and end times. If a job is not processed immediately after its arrival or if its processing is aborted, the job is lost. The goal is to maximize the total value of all processed jobs. In general, this problem does not allow on-line approximations with finite worst case guarantee. We give an approximation algorithm with worst case ratio four for large classes of special instances, and we also prove that the factor four is best possible. One of our classes contains the instances where the job values are proportional to the job lengths.
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
on-line scheduling problemReferences:
| [1] | Arkin, E. A.; Silverberg, E. B., Scheduling jobs with fixed start and end times, Discrete Appl. Math., 18, 1-8 (1987) · Zbl 0636.90042 |
| [2] | Baeza-Yates, R. A.; Culberson, J. C.; Rawlins, G. J.E., Searching with uncertainty, Proc. Scandinavian Workshop on Algorithm Theory, 176-189 (1988) · Zbl 0651.68111 |
| [3] | Ben-David, S.; Borodin, A.; Karp, R.; Tardos, G.; Widgerson, A., On the power of randomization in on-line algorithms, Proc. 22nd Ann. Symp. on Theory of Computing, 379-386 (1990) |
| [4] | Faigle, U.; Nawijn, W. M., Greedy \(k\)-coverings of interval orders, (Tech. Report 979 (1991), University of Twente) · Zbl 0928.68125 |
| [5] | Johnson, D. S.; Demers, A.; Ullman, J. D.; Garey, M. R.; Graham, R. L., Worst case performance bounds for simple one-dimensional bin packing algorithms, SIAM J. Comput., 3, 299-325 (1974) · Zbl 0297.68028 |
| [6] | Kierstead, H. A., An effective version of Dilworth’s theorem, Trans. Amer. Math. Soc., 268, 63-77 (1981) · Zbl 0485.03019 |
| [7] | Lovász, L.; Saks, M.; Trotter, W. T., An on-line graph coloring algorithm with sublinear performance ratio, Discrete Math., 75, 319-325 (1989) · Zbl 0679.05031 |
| [8] | Manasse, M.; McGeoch, L.; Sleator, D., Competitive algorithms for on-line problems, Proc. 20th Ann. Symp. on Theory of Computing, 322-333 (1988) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
