This paper considers the scheduling problem of minimizing the maximum stretch on a single machine with release dates. The need to give importance to short jobs in interactive environments where jobs with long and short processing times are involved creates a Scheduling problem. Also this problem, is by nature NP-Hard (difficult to achieve optimal solutions in good time).Hence, the John Gbeminiyi Oyewole 1(JGO1) heuristic was developed to solve this problem. JGO1 heuristic and two other solution methods selected from the literature (First in First out (FIFO) and Branch and Bound (BB)) were tested on 1400 randomly generated problems. Twenty Eight different problem sizes ranging from 3 to 500 jobs and 50 problem instances under each problem size were generated. Performance evaluation was based on effectiveness and efficiency of the solution methods. Experimental results based on effectiveness show that JGO1 performed competitively with the BB method (BB not significantly different from JGO1 at 5% level), but far better than FIFO for 3 to 500 problem sizes. However, the JGO1 achieved a lesser mean best-result than the BB method. Based on efficiency, JGO1 and FIFO were faster than the BB method but not significantly different from each other at 5% level.
:Scheduling, Maximum Stretch, Starvation, Heuristics, Efficiency, Effectiveness
G.J.Oyewole, A.E. Oluleye, E.O. Oyetunji, Minimizing Maximum Stretch on A Single Machine with Release Dates, Advances in Industrial Engineering and Management, Vol.3, No.1, 2014, pp.1-12, doi: 10.7508/AIEM-V3-N1-1-12.
(size: 305.83 kB, pp.1-12
, Download times:
 Z. K. Huang and K. W. Chau, 2008, ‘A New Image Thresholding Method Based on Gaussian Mixture Model’, Applied Mathematics and Computation, pp. 899-907.
 Wu, C.L., Chau, K.W., and Li, Y.S, 2009. ‘Predicting monthly streamflow using data-driven models coupledwith data-preprocessing techniques’ Water Resources Research 45, W08432, doi: 10. 1029 /2007 WR006737.
 J. Zhang. and K. w Chau, 2009, ‘Multilayer Ensemble Pruning via Novel Multi-sub-swarm Particle Swarm Optimization’ Journal of Universal Computer Science, pp:840-858.
 R. Taormina, K. Chau, and R. Sethi, 2012, ‘Artificial Neural Network simulation of hourly groundwater levels in a coastal aquifer system of the Venice lagoon’ Engineering Applicati-ons of Artificial Intelligence pp: 1670-1676.
 M. Olya, B. Shirazi, H. Fazlollahtabar, 2013, ‘Adapted Dynamic Program to Find Shortest Path in a Network having Normal Probability Distribution Arc Length’ Advances in Industrial Engineering and Management, pp:5-10.
 E.O.Oyetunjiand A.E. Oluleye, 2011, ‘Minim-izing Total Earliness and Total Tardiness on single machine with release dates’, International Journal of Engineering Research in Africa, pp30-43.
 E.O.Oyetunji, 2009, ‘Some common perform-ance measures in scheduling problems’. Research Journal of applied sciences, Engineering and Technology. pp:6-9.
 J.H,Steckel, R S. Winer, R E. Bucklin, B. G. C. Dellaert, X. Dr`Eze, G. Ha¨ Ubl , S. D. Jap, J. D. C. Little, T.Meyvis,A. L Montgomery, and A .Rangaswamy. 2005, ‘Choice in Interactive Environments Springer Science + Business Media, Inc’. Marketing Letters, pp: 309–320.
 M. A. Bender, S.Chakrabarti and S. Muthukrishnan. 1998, ‘Flow and stretch metrics for scheduling continuous job streams’. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. pp270–279.
 M.Mastrolilli, 2004, ‘Scheduling to minimize max flow time: Off-line and on-line algorithms’. International Journal of Foundations of Computer Science, pp:385–401.
 N.Bansal, 2003, ‘Algorithms for Flow Time Scheduling’ John Wiley and Sons, New York.
 F.Vivien, A.Legrandand A. Su, 2005, ‘On-line scheduling of divisible requests on an heterogeneous collection of databanks’. In Proceedings of the 14th Heterogeneous Computing Workshop, Denver, Colorado, USA, IEEE Computer Society Press.
 M.Pinedo, 1995, sScheduling Theory, Algorithms and Systems’. Prentice Hall.
 M.Mastrolilli and C. Ambuhl. 2005. ‘Online Scheduling to minimize max flow time: an optimal preemptive algorithm’. Elsevier B.V. pp:597–602.
 Vivien, F., Legrand, A., and Su, A., 2004, ‘On-line scheduling of divisible requests on an heterogeneous collection of databanks’. Research report 5386, INRIA, (2004).Also available as LIP, ENS Lyon, research report. 2004-51.
 E.O.Oyetunji, and A. E. Oluleye, 2007, ‘Heur-istics for minimizing total completion time on single machine with release time’. Adv. Mater. Res. pp:347-352.
 E.O.Oyetunji and A.E.Oluleye, 2012, ‘A Generalized Algorithm for Solving Multicriteria Scheduling Problems’. Advanced Materials Research, Trans Tech Publications Ltd., Switzerland. pp: 653-666.
 R.L. Graham, E.L.Lawler, J.K.Lenstra, and A.H.G.Rinnooykan, 1979, Optimiz-ation and approximation in determin-istic sequencing and scheduling: a survey.Ann. Discrete. Math. pp:287-326.
 E.O. Oyetunji and M. Mashaudu. 2009, ‘An Improved Heuristic for Minimizing Total Completion Time on Single Machine with Release Time’. Research Journal of Mathematics and Statistics. pp.,65-68.
 S.French. 1982, ‘Sequencing and Scheduling’, Ellis Horwwod.
 M. A.Bender, S.Chakrabarti, and S. Muthukrishnan. 2002. ‘Improved algorithms for stretch scheduling. Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms,Philadelphia, PA, USA, Society for Industrial and Applied.