The sequencing of groups of jobs on a workstation, when each group is periodically released, is a common scheduling practice in manufacturing.  When the objective is to minimize the sum of completion time, it becomes an NP-Hard problem.  Solution to small instances of this problem, and most NP-Hard problems, can be found using integer programming algorithms such as branch-and-bound or cutting plane strategies.  However large instances must settle for an approximate algorithm using some heuristic or dispatch rule. 

In this paper, we present a composite dynamic dispatch rule named “Gap or No Gap” (GORNG) for tight schedules of large instances of the 1 | r_j | ? C_j problem that performs better than other commonly used approaches. Our approach is novel in that it is counter-intuitive to keep a machine idle sometimes when work is available.  We prove that in some cases it is better to force idle time rather than to schedule the next available job when the goal is to minimize the sum of the completion times of all jobs.  The proposed Composite Dynamic Dispatching Rule (GORNG) was tested using four randomly generated datasets. The results prove that our rule consistently performed better than both the Gap (G) and the No Gap (NG) rule. In the four data sets, GORNG was better 75.00%, 72.73%, 85.16%, and 71.88% of the time with reference to our objective of minimizing the completion time.

Since most scheduling scenarios involve future demand that is not always known in advance, our proposed dispatch rule “Gap or No Gap” (GORNG) provides a better strategy with reference to the objective. Our proposed algorithm has important applications in practice. Operations Managers should realize that scheduling all unfinished jobs on hand does not guarantee an optimal solution all the time as there are certain instances where it is better to force idle time rather than scheduling all the unfinished jobs.

Keywords :
Scheduling, Release Dates, Single Workstation, Completion Time, Composite Dynamic Dispatching Rule.