×

The joint load balancing and parallel machine scheduling problem. (English) Zbl 1421.90064

Hu, Bo (ed.) et al., Operations research proceedings 2010. Selected papers of the annual international conference of the German Operations Research Society (GOR), Universität der Bundeswehr München, September 1–3, 2010. Berlin: Springer. Oper. Res. Proc., 497-502 (2011).
Summary: 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 C. Koulamas [Oper. Res. 42, No. 6, 1025–1041 (1994; Zbl 0824.90083)] for the problem of total tardiness minimization. The obtained results are promising.
For the entire collection see [Zbl 1220.90005].

MSC:

90B35 Deterministic scheduling theory in operations research

Citations:

Zbl 0824.90083

Software:

CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Azizoǧlu and O. Kirca. Tardiness minimization on parallel machines. International Journal of Production Economics, 55: 163-168, 1998. · doi:10.1016/S0925-5273(98)00034-6
[2] 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. · Zbl 0949.90642 · doi:10.1080/002075499191517
[3] C. Koulamas. The total tardiness problem: review and extensions. Operations Research, 42:1025-1041,1994. · Zbl 0824.90083 · doi:10.1287/opre.42.6.1025
[4] 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. · Zbl 1142.90387 · doi:10.1016/j.ejor.2005.06.025
[5] 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. · doi:10.1016/0925-5273(94)90048-5
[6] S. Rajakumar, V.P. Arunachalam, and V. Selladurai. Workflow balancing strategies in parallel machine scheduling. International Journal of Advanced Manufacturing, 23: 366-374, 2004. · doi:10.1007/s00170-003-1603-4
[7] 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. · doi:10.1007/s00170-006-0553-z
[8] 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.
[9] K.E. Stecke. Formulation and solution of nonlinear integer production planning problems for flexible manufacturing systems. Management Science, 29: 273-289, 1983. · Zbl 0517.90035 · doi:10.1287/mnsc.29.3.273
[10] 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. · doi:10.1016/j.ijpe.2004.01.003
[11] 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. · Zbl 1094.90548 · doi:10.1080/002075400418298
[12] F. Yalaoui and C. Chu. Parallel machine scheduling to minimize total tardiness. International Journal of Production Economics, 76: 265-279, 2002. · doi:10.1016/S0925-5273(01)00175-X
[13] 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. · Zbl 1143.90342
[14] 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.
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.