Minimizing Maximum Stretch on A Single Machine with Release Dates

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.