Minimization of Total Tardiness and Total Flowtime on Single Machine with Non-Zero Release Dates

Abstract:

This paper considers the bicriteria scheduling problem of minimizing the composite function of total tardiness and total flow time on single machine with non-zero release dates. The problem is strongly Non Polynomial (NP). Thus, two heuristics SA7 and SA8 were proposed to solve the problem. The generalized algorithm and the branch and bound procedure were also implemented. The four solution methods were tested on a total of 800 randomly generated problems ranging from 5 to 1000 jobs. Results based on effectiveness and efficiency show that the SA7 heuristic is the most suited solution method to solve the problem.

• Periodical: International Journal of Engineering Research in Africa (Volume 29)
• Pages: 154-164
• DOI: https://doi.org/10.4028/www.scientific.net/JERA.29.154
• Online since: March 2017
• Authors: Saheed Akande*, Ayodeji Emmanuel Oluleye, Elkanah Oyetunji
• Keywords: Bicriteria, Composite Function, Effectiveness, Efficiency

References

[1] R., M'Hallah, Minimizing total earliness and tardiness on a single machine using a hybrid heuristic Computers & Operations Research. 34(2007) 3126–3142.

DOI: 10.1016/j.cor.2005.11.021

[2] I. Al-Harkan, & A. Badiru, Knowledge-Based Approach to machine sequencing. Engineering Design and automation 11 (1995). 43-58.

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

[4] M.T. Tabucanon, and A.A. Cenna, Bicriterion scheduling problem in a job shop with parallel processor International journal of Production Economics, 251(1991) 95-101.

DOI: 10.1016/0925-5273(91)90135-g

[5] W. E., Smith, Various Optimizers for Single-Stage Production. Naval Research Logistic Quarter, 31(1956)59-66.

[6] K.R. Baker, & J.W. Bertrand, A Dynamic Priority Rule for Scheduling against Due-dates. Journal of Operational Management, 31 (1982) 37-42.

DOI: 10.1016/0272-6963(82)90020-1

[7] L. N. Van Wassenhove, & F. Gelders, Solving a Bicriterion scheduling problem. European Journal of Operational Research, 41(1980) 42-48.

DOI: 10.1016/0377-2217(80)90038-7

[8] Erenay, F.S., Sabuncuoglu, I., Toptal, A. & Tiwari, M.K. New solution methods for single machine bi-criteria Scheduling problem: Minimization of average flow time and number of tardy. European Journal of Operation Research, 201(2010) 89 – 98.

DOI: 10.1016/j.ejor.2009.02.014

[9] E.O. Oyetunji, & A.E. Oluleye, Heuristics for minimizing the total completion time and the number of tardy jobs simultaneously on single machine with release time. Research Journal of Applied Sciences, 32 (2008. ) 147–152.

DOI: 10.7166/21-2-53

[10] J. Du, & Y.T. Leung, Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, 153(1990) 483–495.

DOI: 10.1287/moor.15.3.483

[11] V.O., Oladokun, O. E, Owaba & F.O. Olaosebikan, A Bi-Criteria algorithm for the simultaneous minimization of makespan and number of tardy jobs on a single machine with sequence dependent set-up time. Research Journal of Applied Science, Engineering and Technology, 39(2011).

[12] S.A. Akande, Oluleye, A.E. & E.O. Oyetunji, Reducibility of Some Multi Criteria Scheduling Problems to Bicriteria Scheduling Problems. Proceedings of the 2014 International Conference on Industrial Engineering and Operations Management Indonesia, (2014).

DOI: 10.1109/ieom.2015.7228107

[13] S.A. Akande, A . E Oluleye, & E. O Oyetunji, On the Reducibility of Some Multi Criteria Scheduling Problems to Bicriteria Scheduling Problems. Proceedings of the 2015 International Conference on Industrial Engineering and Operations Management Hyatt Dubai, (2015).

DOI: 10.1109/ieom.2015.7228107

[14] T. Sen, & O. Dillepan, Bicriterion scheduling problems involving total tardiness and total flow time Journal of information and optimization science, 202(1999) 155-170.

DOI: 10.1080/02522667.1999.10699409

[15] E.O. Oyetunji, & A.E. Oluleye, A Generalized algorithm for solving multicriteria scheduling problems. Advanced Materials Research, 367 (2012) 653-666.

DOI: 10.4028/www.scientific.net/amr.367.653

[16] E.O., Oyetunji, Some common performance measures in scheduling problems. Research Journal of Applied Science, Engineering & Technology. 12(2009. ) 6-9.

[17] E.O. Oyetunji, & A.E. Oluleye, Hierarchical Minimization of Total Completion Time and Number of Tardy Jobs Criteria. Asian Journal of Information Technology, 74(2010) 157-161.

[18] E.O. Oyetunji, Assessing solution methods to mixed multi-objectives scheduling problems. International Journal of Industrial and Systems Engineering, 92(2011) 213-226.

DOI: 10.1504/ijise.2011.042836

[19] J.K., Cochran, H Shwu,. & J.W. Fowler, A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines. Computers and Operations Research, 307 (2003)1087– 1102.

DOI: 10.1016/s0305-0548(02)00059-x

[20] E.O. Oyetunji, & A.E. Oluleye, Evaluating solution methods to bicriteria scheduling problems Advanced Materials Research, 62(2009. ) 577–584.

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

[21] E. O. Oyetunji, A. E. Oluleye, & S.A. Akande, Approximation Algorithms for Minimizing Sum of Flow Time on a Single Machine with Release Dates. International Journal of Modern Engineering Research 23(2012) 687-696.

[22] J.C. Bean& D.H. Hall, Accuracy of the modified due date rule, Department of Industrial and Production Engineering, Michigan University, Technical report. (1985) 85-100.

[23] J.T. Naidu, A Note on a Well-Known Dispatching Rule to Minimise Total Tardiness. International Journal of Management Science. 312(2003) 137–140.

DOI: 10.1016/s0305-0483(03)00020-3

[24] K.R. Baker & D, Trietsch, Principles of sequencing and scheduling. John Wiley & Sons. Ist ed (2013).

[25] M.L. Pinedo. Scheduling – Theory, Algorithms and Systems New York : Springer. (2008).

[26] A. Gürsel, S. X. Yang, O. I. Alhawari, J. Santos, & R. Vazquez, A genetic algorithm approach for minimizing total tardiness in single machine scheduling. International Journal of Industrial Engineering and Management, 33(2012. ), 163-171.

[27] D. H Brian and T. V. Daniel. Essential MATLAB for Engineers and Scientists. 3rd ed. Amsterdam : Butterworth-Heinemann. (2007).

[28] A.O. Festus. Statistical Method. An introduction. International Publisher Ltd. Ist ed (2006).