A Generalized Algorithm for Solving Multicriteria Scheduling Problems

Abstract:

In this paper, the scheduling problem involving optimization of multiple criteria (or objectives) is explored. There are many variants of the problem. The particular variant, in which the objectives are aggregated into a scalar function (with each criterion having weight which denotes its relative importance), is considered. An algorithm which can be used to solve very large classes of the multicriteria scheduling problem is proposed. The proposed algorithm and two solution methods selected from the literature were evaluated on a total of 900 randomly generated multicriteria scheduling problems (ranging from 10 to 500 jobs). Two variants of the release dates (0 – 24 and 0 – 49) are utilized. Results show that the proposed algorithm performed better than the selected solution methods when the total completion time criterion is much more important than the other criteria. However, when the total completion time criterion is much less important than the other criteria, the selected solution methods outperformed the proposed algorithm. The results are consistent under the two variants of the release dates.

• Periodical: Advanced Materials Research (Volume 367)
• Pages: 653-666
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.367.653
• Online since: October 2011
• Authors: Elkanah Oyetunji, Ayodeji Emmanuel Oluleye
• Keywords: Algorithm (GA), Multicriteria, Optimization, Relative Weights, Scalar Function, Scheduling

References

[1] S. French, Sequencing and Scheduling. Ellis Horwood Limited, (1982).

[2] A.E. Oluleye, E.O. Oyetunji, Performance of some static flowshop scheduling heuristics. Directions in Mathematics, (1999), 315-327.

[3] M.L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Prentice-Hall, (2002).

[4] A. Nagar, J. Haddock J. and S. Heragu, Multiple and bicriteria scheduling: A literature survey. European Journal of Operational Research, 81 (1995), 88-104.

DOI: 10.1016/0377-2217(93)e0140-s

[5] C. Stein, J. Wein, On the Existence of Schedules that are Near-Optimal for both Makespan and Total Weighted Completion Time. Operations Research Letters, 21 (1997), 115-122.

DOI: 10.1016/s0167-6377(97)00025-4

[6] P. Uthaisombut, New Directions in Machine Scheduling, PhD Thesis, Michigan State University, USA, (2000).

[7] J.A. Hoogeveen, Multicriteria Scheduling. European Journal of Operational research, 167 (2005), 592-623.

DOI: 10.1016/j.ejor.2004.07.011

[8] B. Molnar, Multi-criteria scheduling of order picking processes with simulation optimization. Periodica Polytechnica SER. TRANSP. ENG., 33 (2005), 59–68.

[9] V. T'kindt, J. C. Billaut, Multicriteria Scheduling: Theory, Models and Algorithms. 2nd Edition. Springer, Berlin, (2006).

[10] D. Petrovic, D. Alejandra, P. Sania, Decision support tool for multi-objective job shop scheduling problems with linguistically quantified decision functions. Decision Support Systems, 43 (2007), 1527-1538.

DOI: 10.1016/j.dss.2006.06.006

[11] S. Chakrabarti, C.A. Phillips, A.S. Schulz, D.B. Shmoys, C. Stein, J. Wein, Improved scheduling algorithms for minsum criteria. In F. Meyer auf der Heide and B. Monien, editors, Automata, Languages and Programming, Lecture Notes in Computer Science 1099, 646-657, Berlin, 1996. Springer. Proceedings of the 23rd International Colloquium (ICALP'96), (1996).

DOI: 10.1007/3-540-61440-0_166

[12] J. Aslam, A. Rasala, C. Stein, N. Young, Improved Bicriteria Existence Theorems for Scheduling. In proceedings of the 10th annual ACM-SIAM Symposium on Discrete Algorithms, (1999), 846-847.

[13] A. Rasala, C. Stein, E. Torng, P. Uthaisombut, Existence Theorems, Lower Bounds and Algorithms for Scheduling to Meet Two Objectives, Technical Report, Dartmouth College, Computer Science Technical Report, PCS-TR99 – 347, (1999).

[14] J.A. Hoogeveen, S.L. van de Velde, Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time. Operations Research Letters, 17 (1995), 205–208.

DOI: 10.1016/0167-6377(95)00023-d

[15] E.O. Oyetunji, A.E. Oluleye, Heuristics for Minimizing Total Completion Time and Number of Tardy Jobs Simultaneously on Single Machine with Release Time. Research Journal of Applied Sciences, 3 (2008), 147-152.

DOI: 10.7166/21-2-53

[16] E.O. Oyetunji, A.E. Oluleye, New Heuristics for Minimizing Total Completion Time and Number of Tardy Jobs Criteria on Single Machine with Release Time, South African Journal of Industrial Engineering, 21 (2010), 101-113.

DOI: 10.7166/21-2-53

[17] M. Ehrgott, X. Grandibleux, An Annotated Bibliography of Multiobjective Combinatorial Optimization, Report in Wirtschaftsmathematik, No. 62, Fachbereich Mathematik - Universitat Kaiserslautern, (2000).

[18] S.C. Aggarwal, B.A. MeCarl, The Development and Evaluation of a Cost-Based Composite Scheduling Rule. Naval Research Logistics, 21 (1974), 155-169.

DOI: 10.1002/nav.3800210111

[19] C. Chuen-Lung, R.L. Bulfin, Complexity of single machine, multi-criteria scheduling problems, European Journal of Operational Research, 70 (1993), 115-125.

DOI: 10.1016/0377-2217(93)90236-g

[20] F. Sivrikaya, U. Gunduz, A bicriteria two-machine permutation flowshop problem, European Journal of Operational Research, 107 (1998), 414-430.

DOI: 10.1016/s0377-2217(97)00338-x

[21] S. Sayin, S. Karabati, A Bicriteria Approach to the 2-machine flowshop Scheduling problem, European Journal of Operational Research, 113 (1999), 435–449.

DOI: 10.1016/s0377-2217(98)00009-5

[22] C. Chekuri, R. Motwani, B. Natarajan, C. Stein, Approximation techniques for Average Completion Time Scheduling. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, (1997), 609 – 618.

DOI: 10.1137/s0097539797327180

[23] E.O. Oyetunji, A.E. Oluleye, Hierarchical Minimization of Total Completion time and Number of Tardy Jobs Criteria. Asian Journal of Information Technology, 7 (2008), 157-161.

[24] E.O. Oyetunji, A.E. Oluleye, Evaluating Solution Methods to Bicriteria Scheduling Problems. Advanced Materials Research, 62-64 (2009), 577-584.

DOI: 10.4028/www.scientific.net/amr.62-64.577

[25] E.O. Oyetunji, Truncation and Composition of Schedules: A Good Strategy for Solving Bicriteria Scheduling Problems, American Journal of Scientific and Industrial Research 1 (2010), 427-434.

DOI: 10.5251/ajsir.2010.1.3.427.434

[27] E.O. Oyetunji, A.E. Oluleye, Heuristics for minimizing total completion time on single machine with release time. Advanced Materials Research, 18-19 (2007), 347-352.

DOI: 10.4028/www.scientific.net/amr.18-19.347