International Journal of Nonlinear Analysis and Applications

Theoretical approaches and special cases for a single machine with release dates to minimize four criterion

Document Type : Research Paper

Authors

Department of Mathematics, College of Sciences, Al-Mustansireah University, Baghdad, Iraq

Abstract

We propose a multi-objective machine scheduling problem (MSP) in this study. The sum of total flow time, total tardiness, total earliness, and total late work is the topic under discussion. With an arbitrary release date, This paper offers a theoretical analysis, discussion, and proofs for a number of special instances that apply to our topic.

Keywords

[1] T.S. Abdul Razaq, S.K. Al Saidy and M.K. Al Zuwaini, Single machine scheduling to minimize total weighted late work with release date, J. Al-Qadisyah Pure Sci. 13(4) (2008) 91–112.
[2] R.H. Ahmadi and B. Uttarayan, Lower bounds for single-machine scheduling problems, Naval Res. Logistics 37(6) (1990) 967–979.
[3] S.P. Ali and M. Bijari, Minimizing maximum earliness and tardiness on a single machine using a novel heuristic approach, Proc. Int. Conf. Indust. Engin. Operat. Manag. (2012).
[4] M.K. Al-Zuwaini and M.K. Mohanned, One machine scheduling problem with release dates and tow criteria, J. Thi-Qar Univ. 6(2) (2011) 1–14.
[5] J. B lazewicz, Scheduling preemptible tasks on parallel processors with information loss, Rech. Tech. Sci. Inf. 3 (1984) 415–420.
[6] C. Briand and O. Samia, Minimizing the number of tardy jobs for the single machine scheduling problem: MIPbased lower and upper bounds, RAIRO-Operat. Res. 47(1) (2013) 33–46.
[7] R. Chandra, On n/1/F dynamic deterministic problems, Naval Res. Logistics Quart. 26(3) (1979) 537–544.
[8] W.Y. Chen and G.N. Sheen, Single-machine scheduling with multiple performance measures: Minimizing jobdependent earliness and tardiness subject to the number of tardy jobs, Int. J. Production Econom. 109(1-2) (2007) 214–229.
[9] C. Chu, A branch-and-bound algorithm to minimize total flow time with unequal release dates, Naval Res. Logistics 39(6) (1992) 859–875.
[10] P.S. Dauzere, Minimizing late jobs in the general one machine scheduling problem, European J. Operat. Res. 81(1) (1995) 134–142.
[11] M.I. Dessouky and S.D. Jitender, Sequencing jobs with unequal ready times to minimize mean flow time, SIAM J. Comput. 10(1) (1981) 192–202.
[12] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.R. Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discrete Math. 5 (1979) 287–326.
[13] R.B. Kethley and A. Bahram, Single machine scheduling to minimize total weighted late work: a comparison of scheduling rules and search algorithms, Comput. Indust. Engin. 43(3) (2002) 509–528.
[14] J.K. Lenstra, A.R.Kan and P. Brucker, Complexity of machine scheduling problems, Ann. Discrete Math. 1 (1977) 343–362.
[15] M. Mahnam and M. Ghasem, A branch-and-bound algorithm for minimizing the sum of maximum earliness and tardiness with unequal release times, Engin. Optim. 41(6) (2009) 521–536.
[16] J.M. Moore, One machine sequencing algorithm for minimizing the number of late jobs, Manag. Sci. 15(1) (1968) 102–109.
[17] C.N. Potts and L.N. Van Wassenhove, Approximation algorithms for scheduling a single machine to minimize total late work, Operat. Rese. Lett. 11(5) (1992) 261–266.
[18] C.N. Potts and L.N. Van Wassenhove, Single machine scheduling to minimize total late work, Operat. Res. 40(3) (1991) 586–595.
[19] A.H.G. Rinnooy Kan, Machine Sequencing Problem: Classification, complexity and computations, 1976.
[20] L. Schrage, Letter to the editor a proof of the optimality of the shortest remaining processing time discipline, Operat. Res. 16(3) (1968) 687–690.
[21] J.B. Sidney, Optimal single-machine scheduling with earliness and tardiness penalties, Operat. Res. 25(1) (1977) 62–69.
International Journal of Nonlinear Analysis and Applications
Volume 13, Issue 1
March 2022
Pages 2075-2085
  • Receive Date: 01 September 2021
  • Revise Date: 19 October 2021
  • Accept Date: 05 November 2021