×

Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints. (English) Zbl 1163.90006

Summary: This paper considers a deterministic scheduling problem where multiple jobs with s-precedence relations are processed on multiple identical parallel machines. The objective is to minimize the total completion time. The s-precedence relation between two jobs \(i\) and \(j\) represents the situation where job \(j\) is constrained from processing until job \(i\) starts processing, which is different from the standard definition of a precedence relation where \(j\) cannot start until \(i\) completes. The s-precedence relation has wide applicability in the real world such as first-come-first-served processing systems.
The problem is shown to be intractable, for which a heuristic procedure is derived. Numerical experiments are conducted to show that the derived heuristic provides effective solutions.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Kim ES, Posner, ME. Parallel machine scheduling with s-precedence constraints, 2007, submitted for publication.; Kim ES, Posner, ME. Parallel machine scheduling with s-precedence constraints, 2007, submitted for publication.
[2] Lawler, E. L., Sequencing jobs to minimize total weighted completion time, Annals of Discrete Mathematics, 2, 75-90 (1978) · Zbl 0374.68033
[3] Horn, W. A., Single-machine job sequencing with treelike precedence ordering and linear delay penalties, SIAM Journal on Applied Mathematics, 23, 189-202 (1972) · Zbl 0224.90025
[4] Adolphson, D.; Hu, T. C., Optimal linear ordering, SIAM Journal on Applied Mathematics, 25, 403-423 (1973) · Zbl 0274.90061
[5] Sidney, J. B., Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs, Operations Research, 23, 283-298 (1975) · Zbl 0304.90058
[6] Chekuri, C.; Motwani, R., Precedence constrained scheduling to minimize sum of weighted completion times on a single machine, Discrete Applied Mathematics, 98, 29-38 (1999) · Zbl 1009.90053
[7] Chudak, F.; Hochbaum, D., A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine, Operations Research Letters, 25, 199-204 (1999) · Zbl 0958.90042
[8] Du, J.; Leung, J. Y.-T.; Young, G. H., Scheduling chain-structured tasks to minimize makespan and mean flow time, Information and Computation, 92, 219-236 (1991) · Zbl 0754.90029
[9] Nilson, N. J., Principles of artificial intelligence (1980), Tioga: Tioga Palo Alto, CA · Zbl 0422.68039
[10] Chang, J.; Hsu, C., Task scheduling with precedence constraints to minimize the total completion time, International Journal Systems Science, 26, 2203-2217 (1995) · Zbl 0836.90093
[11] Dror, M.; Kubiak, W.; Dell’Olmo, P., Scheduling chains to minimize mean flow time, Information Processing Letters, 61, 297-301 (1997) · Zbl 1337.68128
[12] Hall, L. A.; Schulz, A. S.; Shmoys, D. B.; Wein, J., Scheduling to minimize average completion time: offline and online algorithms, Mathematics of Operations Research, 22, 513-544 (1997) · Zbl 0883.90064
[13] Ramachandra, G.; Elmaghraby, S. E., Sequencing precedence-related jobs on two machines to minimize the weighted completion time, International Journal of Production Economics, 100, 44-58 (2006)
[14] Queyranne, M.; Schulz, A. S., Approximation bounds for a general class of precedence constrained parallel machine scheduling problems, SIAM Journal on Computing, 35, 1241-1253 (2006) · Zbl 1100.68010
[15] Graham, R. L., Bounds on multiprocessing timing anomalies, SIAM Journal on Applied Mathematics, 17, 416-429 (1969) · Zbl 0188.23101
[16] Smith, W. E., Various optimizer for single stage production, Naval Research Logistics Quartely, 3, 59-66 (1956)
[17] Conway, R. W.; Maxwell, W. L.; Miller, L. W., Theory of scheduling (1967), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 1058.90500
[18] Graham, R. L., Bounds for certain multiprocessing anomalies, Bell System Technical Journal, 45, 1563-1581 (1966) · Zbl 0168.40703
[19] Schulz AS. Scheduling to minimize total weighted completion time: performance guarantees of LP-based heuristics and lower bounds. In: Cunningham WH, McCormick ST, Queyranne M, editors. Integer programming and combinatorial optimization. Lecture notes in computer science, vol. 1084. Berlin: Springer; 1996. p. 119-33.; Schulz AS. Scheduling to minimize total weighted completion time: performance guarantees of LP-based heuristics and lower bounds. In: Cunningham WH, McCormick ST, Queyranne M, editors. Integer programming and combinatorial optimization. Lecture notes in computer science, vol. 1084. Berlin: Springer; 1996. p. 119-33.
[20] Hall, N. G.; Posner, M. E., Generating experimental data for computational testing with machine scheduling applications, Operations Research, 49, 854-865 (2001) · Zbl 1163.90490
[21] Garey, M. R.; Johnson, D. S., Computers and intractability: a guide to the theory of NP-completeness (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039
[22] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic machine scheduling: A survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044
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.