Preemptive scheduling with availability constraints to minimize total weighted completion times. (English) Zbl 1119.90023
Summary: In this paper we study the problem of scheduling \(n\) jobs on a single machine with availability constraints. The objective is to minimize total weighted job completion times. We show that the problem is NP-hard in the strong sense. Then we consider two intractable special cases, namely, proportional weight case, and single availability constraint case. We propose two heuristics for these cases and analyze their worst-case error bounds.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Adiri, I., J. Bruno, and A.H.G. Rinnooy Kan. (1989). ”Single Machine Flow-Time Scheduling with a Single Breakdown.” Acta Informatica 26, 679–696. · Zbl 0657.68033 · doi:10.1007/BF00288977 |
| [2] | Garey, M.R. and D.S. Johnson. (1979). Computer and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, CA: Freeman. · Zbl 0411.68039 |
| [3] | Goemans, M.X., M. Queyranne, A.S. Schulz, M. Skutella, and Y. Wang. (2002). ”Single Machine Scheduling with Release Dates.” SIAM Journal on Discrete Mathematics 15, 165–192. · Zbl 1009.90096 · doi:10.1137/S089548019936223X |
| [4] | Goemans, M.X., J.M. Wein, and D.P. Williamson. (2000). ”A 1.47 Approximation Algorithm for a Preemptive Single-Machine Scheduling Problem.” Operations Research Letters 26, 149–154. · Zbl 0955.90025 · doi:10.1016/S0167-6377(00)00024-9 |
| [5] | Graham, R.L., E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan. (1979). ”Optimization and Approximation in Deterministic Machine Scheduling: A Survey.” Annals of Discrete Mathematics 5, 287–326. · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [6] | Lee, C.-Y. (1996). ”Machine Scheduling with an Availability Constraint.” Journal of Global Optimization 9, 395–416. · Zbl 0870.90071 · doi:10.1007/BF00121681 |
| [7] | Lee, C.-Y., L. Lei, and M. Pinedo. (1997). ”Current Trends in Deterministic Scheduling.” Annals of Operations Research 70, 1–42. · Zbl 0890.90102 · doi:10.1023/A:1018909801944 |
| [8] | Lee, C.-Y. and S.D. Liman. (1992). ”Single Machine Flowtime Scheduling with Scheduled Maintenance.” Acta Informatica 29, 375–382. · doi:10.1007/BF01178778 |
| [9] | Sanlaville, E. and G. Schmidt. (1998). ”Machine Scheduling with Availability Constraints.” Acta Informatica 35, 795–811. · Zbl 0917.68018 · doi:10.1007/s002360050143 |
| [10] | Schmidt, G. (2000). ”Scheduling with Limited Availability.” European Journal of Operational Research 121, 1–15. · Zbl 0959.90023 · doi:10.1016/S0377-2217(98)00367-1 |
| [11] | Schulz, A.S. and M. Skutella. (1997). ”The Power of {\(\alpha\)}-Points in Preemptive Single Machine Scheduling.” Technical Report, Technische Universität Berlin, Fachbereich Mathematik. · Zbl 1038.90037 |
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.
