Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. (English) Zbl 1009.90053
Summary: We consider the problem of scheduling a set of jobs on a single machine with the objective of minimizing sum of weighted completion times. The problem is NP-hard when there are precedence constraints between jobs [E. L. Lawler, Ann. Discrete Math. 2, 75-90 (1978; Zbl 0374.68033)]. We provide an efficient combinatorial 2-approximation algorithm for this problem. In contrast to our work, earlier approximation algorithms [A. Hall, A. S. Schulz, D. B. Shmoys and J. Wein, Math. Oper. Res. 22, 513-544 (1997; Zbl 0883.90064)] achieving constant factor approximations are based on solving a linear programming relaxation of the problem. We also show that the linear ordering relaxation of C. N. Potts [Math. Program. Stud. 13, 78-87 (1980; Zbl 0441.90038)] has an integrality gap of 2.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90B22 | Queues and service in operations research |
References:
| [1] | Adolphson, D., Single machine job sequencing with precedence constraints, SIAM J. Comput., 6, 40-54 (1977) · Zbl 0348.68033 |
| [5] | Du, J.; Leung, J. Y.T; Young, G. H., Scheduling chain structured tasks to minimize makespan and mean flow time, Inform. Comput., 92, 219-236 (1991) · Zbl 0754.90029 |
| [6] | Gallo, G.; Grigoriadis, M. D.; Tarjan, R., A fast parametric maximum flow algorithm and applications, SIAM J. Comput., 18, 30-55 (1989) · Zbl 0679.68080 |
| [7] | Garey, M. R., Optimal task sequencing with precedence constraints, Discrete Math., 4, 37-56 (1973) · Zbl 0253.90057 |
| [10] | Goldberg, A. V.; Tarjan, R. E., A new approach to the maximum flow problem, J. Assoc. Comput. Mach., 35, 921-940 (1988) · Zbl 0661.90031 |
| [11] | Hall, L. A.; Schulz, A. S.; Shmoys, D. B.; Wein, J., Scheduling to minimize average completion time: offline and online algorithms, Math. Oper. Res., 22, 513-544 (1997) · Zbl 0883.90064 |
| [12] | Horn, W. A., Single-machine job sequencing with treelike precedence ordering and linear delay penalties, SIAM J. Appl. Math., 23, 189-202 (1972) · Zbl 0224.90025 |
| [13] | Hu, T. C., Parallel sequencing and assembly line problems, Oper. Res., 9, 841-848 (1961) |
| [15] | Lawler, E. L., Sequencing jobs to minimize total weighted completion time, Ann. Discrete Math., 2, 75-90 (1978) · Zbl 0374.68033 |
| [19] | Potts, C. N., An algorithm for the single machine sequencing problem with precedence constraints, Math. Prog. Stud., 13, 78-87 (1980) · Zbl 0441.90038 |
| [21] | Smith, W., Various optimizers for single-stage production, Nav. Res. Logist. Quart., 3, 59-66 (1956) |
| [22] | Sydney, J., Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs, Oper. Res., 23, 2, 283-298 (1975) · Zbl 0304.90058 |
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.
