Abstract
The addressed problem in this paper considers the joint load balancing and parallel machines scheduling problem. Two decisions are taken at once: to build the best schedule of n jobs on m identical parallel machines in order to minimize the total tardiness and to find the equitable distribution of the machine’s time activity. To our knowledge, these two criteria have never been simultaneously studied for the case of parallel machines. The considered problem is NP-hard since the problem with only the total tardiness minimization is NP-hard. We propose an exact and an approached resolution. The first method is based on the mixed integer linear programming method solved by Cplex solver. The second one is an adapted genetic algorithm. The test examples were generated using the schema proposed by Koulamas [3]for the problem of total tardiness minimization. The obtained results are promising.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Azizoǧlu and O. Kirca. Tardiness minimization on parallel machines. International Journal of Production Economics, 55: 163–168, 1998.
R.R. Gung and H.J. Steudel. A workload balancing model for determining set-up time and batch size reductions in GT flow line work cells. International Journal of Production Research, 37(4): 769–791, 1999.
C. Koulamas. The total tardiness problem: review and extensions. Operations Research, 42:1025–1041,1994.
A. Kumar, Prakash, M. Tiwari, R. Shankar, and A. Baveja. Solving machine loading problems in a flexible manufacturing system using a genetic algorithm based heuristic approach. European Journal of Operational Research, 175: 1043–1069, 2006.
B.K. Modi and K. Shanker. A formulation and solution methodology for part movement minimization and workload balancing at loading decisions in FMS. International Journal of Production Economics, 34: 73–82, 1994.
S. Rajakumar, V.P. Arunachalam, and V. Selladurai. Workflow balancing strategies in parallel machine scheduling. International Journal of Advanced Manufacturing, 23: 366–374, 2004.
S. Rajakumar, V.P. Arunachalam, and V. Selladurai. Workflow balancing in parallel machines through genetic algorithm. International Journal of Advanced Manufacturing Technology, 33: 1212–1221, 2007.
K. Shanker and S. Rajamathanandan. Loading problemin FMS: part movement minimization. In Proc. 3rd ORSA/TIMS conf. on flexible manufacturing systems: Operations Research Models and Applications, pages 99–104, 1989.
K.E. Stecke. Formulation and solution of nonlinear integer production planning problems for flexible manufacturing systems. Management Science, 29: 273–289, 1983.
D.S. Sun, T.E. Lee, and K.H. Kim. Component allocation and feeder arrangement for a dual-gantry multi-head surface mounting placement tool. International Journal of Production Economics, 95: 245–264, 2005.
M.K. Tiwari and N.K. Vidyarthi. Solving machine loading problems in a flexible manufacturing system using a genetic algorithm based heuristic approach. International Journal of Production Research, 38(14): 3357–3384, 2000.
F. Yalaoui and C. Chu. Parallel machine scheduling to minimize total tardiness. International Journal of Production Economics, 76: 265–279, 2002.
M.B. Yildirim, E. Duman, K. Krishna, and K. Senniappan. Parallel machine scheduling with load balancing and sequence dependent setups. International Journal of Operations Research, 4: 42–49, 2007.
L. YU, M. Shih, M. Pfund, M.W. Carlyle, and W.J. Fowler. Scheduling unrelated parallel machines: an application to PWB manufacturing. IIE Transactions, 34: 921–931, 2002.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ouazene, Y., Hnaien, F., Yalaoui, F., Amodeo, L. (2011). The Joint Load Balancing and Parallel Machine Scheduling Problem. In: Hu, B., Morasch, K., Pickl, S., Siegle, M. (eds) Operations Research Proceedings 2010. Operations Research Proceedings. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20009-0_79
Download citation
DOI: https://doi.org/10.1007/978-3-642-20009-0_79
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20008-3
Online ISBN: 978-3-642-20009-0
eBook Packages: Business and EconomicsBusiness and Management (R0)