Abstract
A new n log n algorithm for the scheduling problem of n independent jobs on m identical parallel machines with minimum makespan objective is proposed and its worst-case performance ratio is estimated. The algorithm iteratively combines partial solutions that are obtained by partitioning the set of jobs into suitable families of subsets. The computational behavior on three families of instances taken from the literature provided interesting results.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anderson, E.J., Glass, C.A., Potts, C.N.: Machine scheduling. In: Aarts, Lenstra (eds.) Local Search in Combinatorial Optimization, pp. 361–414. Wiley, New York (1997)
Chen, B., Potts, C.N., Woeginger, G.J.: A review of machine scheduling: complexity, algorithms and approximability. In: Du, D.Z., Pardalos, P. (eds.) Handbook of Combinatorial Optimization, vol. 3, pp. 21–169. Kluwer Academic, Dordrecht (1998)
Cheng, T., Sin, C.: A state of the art review of parallel machine scheduling research. Eur. J. Oper. Res. 47, 271–292 (1990)
Coffman, E.G. Jr., Garey, M.R., Johnson, D.S.: An application of bin-packing to multiprocessor scheduling. SIAM J. Comput. 7, 1–17 (1978)
Coffman, E.G. Jr., Sethi, R.: A generalized bound on LPT sequencing. RAIRO-Inform. 10, 17–25 (1976)
França, P.M., Gendrau, M., Laporte, G., Muller, F.M.: A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective. Comput. Ops. Res. 21(2), 205–210 (1994)
Frangioni, A., Scutellà, M.G., Necciari, E.: Multi-exchange algorithms for the minimum makespan machine. Technical Report:99-22, Dipartimento di Matematica. University of Pisa, Italy (1999)
Frangioni, A., Necciari, E., Scutellà, M.G.: A multi-exchange neighborhood for minimum makespan machine scheduling problems. J. Comb. Optim. 8, 195–220 (2004)
Friesen, D.K.: Tighter bounds for the MultiFit processor scheduling algorithm. SIAM J. Comput. 13, 170–181 (1984)
Garey, M.R., Johnson, D.S.: Computers and Intractability: a Guide to the Theory of NP-completeness. Freeman, San Francisco (1979)
Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563–1581 (1966)
Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17, 416–429 (1969)
Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling a survey. Ann. Discrete Math. 5, 287–326 (1979)
Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. Assoc. Comput. Mach. 34, 144–162 (1987)
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: algorithms and complexity in logistics of production and inventory. In: Handbooks in Operation Research and Management Science, vol. 4, pp. 445–522. Elsevier Science, Amsterdam (1993)
Leung, J. (ed.): Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman & Hall/CRC, Boca Raton (2004)
Paletta, G., Pietramala, P.: A new approximation algorithm for the non-preemptive scheduling of independent jobs on identical parallel processors. SIAM J. Discrete Math. 21, 313–328 (2007)
Ullman, J.D.: Complexity of sequencing problems. In: Coffman, E.G. (ed.) Computer and Job Shop Scheduling Theory, pp. 139–164. Wiley, New York (1976)
Yue, M.: On the exact upper bound for the MultiFit processor scheduling algorithm. Ann. Oper. Res. 24, 233–259 (1990)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chiaselotti, G., Gualtieri, M.I. & Pietramala, P. Minimizing the Makespan in Nonpreemptive Parallel Machine Scheduling Problem. J Math Model Algor 9, 39–51 (2010). https://doi.org/10.1007/s10852-009-9120-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10852-009-9120-6