Journal of Software, Vol 6, No 6 (2011), 1146-1153, Jun 2011
doi:10.4304/jsw.6.6.1146-1153

A Heuristic Serial Schedule Algorithm for Unrelated Parallel Machine Scheduling With Precedence Constraints

Chunfeng Liu, Shanlin Yang

Abstract


The paper presents a priority rule-based heuristic serial schedule (SS) algorithm for a deterministic scheduling problem where multiple jobs with arbitrary precedence constraints are processed on multiple unrelated parallel machines. The objective is to minimise makespan. The priority rule employs the arithmetic mean and deviation of the processing times to determine the prior job-machine pair. Moreover, at each iteration, the algorithm can schedule the prior job on the prior machine as early as possible to prevent certain machines from standing idle by the greatest extent. The proposed algorithm is demonstrated in detail through a test instance. Computational experiments are conducted to show that the new polynomial-time algorithm is effective in reducing makespan and efficient in shortening runtime.


Keywords


unrelated machines; scheduling; precedence constraints; makespan; priority rule; heuristics

References


[1] W. A. Horn, “Single-machine job sequencing with treelike precedence ordering and linear delay penalties,” SIAM Journal on Applied Mathematics, vol. 23, pp. 189–202, 1972.
doi:10.1137/0123021

[2] E. L. Lawler, “Sequencing jobs to minimize total weighted completion time subject to precedence constraints,” Annals of Discrete Mathematics, vol. 2, pp. 75–90, 1978.
doi:10.1016/S0167-5060(08)70323-6

[3] D. Adolphson and T. C. Hu, “Optimal linear ordering,” SIAM Journal on Applied Mathematics, vol. 25, pp. 403–423, 1973.
doi:10.1137/0125042

[4] J. B. Sidney, “Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs,” Operations Research, vol. 23, pp. 283–298, 1975.
doi:10.1287/opre.23.2.283

[5] F. A. Chudak and D. S. Hochbaum, “A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine,” Operations Research Letters, vol. 25, pp. 199–204, 1999.
doi:10.1016/S0167-6377(99)00056-5

[6] I. D. Baev, W. M. Meleis, and A. Eichenberger, “Lower bounds on precedence-constrained scheduling for parallel processors,” Information Processing Letters, vol. 83, pp. 27–32, 2002.
doi:10.1016/S0020-0190(01)00303-9

[7] F. A. Chudak and D. B. Shmoys, “Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds,” Journal of Algorithms, vol. 30, pp. 323–343, 1999.
doi:10.1006/jagm.1998.0987

[8] I. Aho and E. Mäkinen, “On a parallel machine scheduling problem with precedence constraints,” Journal of Scheduling, vol. 9, pp. 493–495, 2006.
doi:10.1007/s10951-006-8499-4

[9] J. Du, J. Y. T. Leung, and G. H. Young, “Scheduling chain-structured tasks to minimize makespan and mean flow time,” Information and Computation, vol. 92, pp. 219–236, 1991.
doi:10.1016/0890-5401(91)90009-Q

[10] J. M. Chang and C. C. Hsu, “Task scheduling with precedence constraints to minimize the total completion time,” International Journal Systems Science, vol. 26, pp. 2203–2217, 1995.
doi:10.1080/00207729508929163

[11] G. Ramachandra and S. E. Elmaghraby, “Sequencing precedence-related jobs on two machines to minimize the weighted completion time,” International Journal of Production Economics, vol. 100, pp. 44–58, 2006.
doi:10.1016/j.ijpe.2004.10.014

[12] M. Queyranne and A. S. Schulz, “Approximation bounds for a general class of precedence constrained parallel machine scheduling problems,” SIAM Journal on Computing, vol. 35, no. 5, pp. 1241–1253, 2006.
doi:10.1137/S0097539799358094

[13] L. A. Hall, A. S. Schulz, and D. B. Shmoys, “Scheduling to minimize average completion time: offline and online algorithms,” Mathematics of Operations Research, vol. 22, pp. 513–544, 1997.
doi:10.1287/moor.22.3.513

[14] M. Queyranne and M. Sviridenko, “Approximation algorithms for shop scheduling problems with minsum objective,” Journal of Scheduling, vol. 5, pp. 287–305, 2002.
doi:10.1002/jos.96

[15] E. S. Kim and M. E. Posner, “Parallel machine scheduling with s-precedence constraints,” IIE Transactions, vol. 42, pp. 525–537, 2010.
doi:10.1080/07408171003670975

[16] E. S. Kim, C. S. Sung, and I. S. Lee, “Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints,” Computers & Operations Research, vol. 36, pp. 698–710, 2009.
doi:10.1016/j.cor.2007.10.025

[17] J. Herrmann, J. M. Proth, and N. Sauer, “Heuristics for unrelated machine scheduling with precedence constraints,” European Journal of Operational Research, vol. 102, pp. 528–537, 1997.
doi:10.1016/S0377-2217(96)00247-0

[18] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. R. Kan, “Optimization and approximation in deterministic sequencing and scheduling: A survey,” Annals of Discrete Mathematics, vol. 5, pp. 287–326, 1979.
doi:10.1016/S0167-5060(08)70356-X

[19] J. D. Ullman, “NP-complete scheduling problems,” Journal of Computer and System Sciences, vol. 10, pp. 384– 393, 1975.
doi:10.1016/S0022-0000(75)80008-0

[20] R. Tavakkoli-Moghaddam, F. Taheri, M. Bazzazi, M. Izadi, and F. Sassani, “Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints,” Computers & Operations Research, vol. 36, pp. 3224–3230, 2009.
doi:10.1016/j.cor.2009.02.012


Full Text: PDF


Journal of Software (JSW, ISSN 1796-217X)

Copyright @ 2006-2013 by ACADEMY PUBLISHER – All rights reserved.