Dynamic analysis to set idle time between jobs on a single machine

Scheduling problems are common phenomena in everyday life. Most of the scheduling algorithms do not allow the resources to be kept idle when the jobs are waiting for its turn. However, scheduling of jobs with idle time insertion is desirable when early penalties are significantly large. Instead of starting a job immediately, deferring it for a while may facilitate to meet its due date. The problem considered here is to find the optimal schedule so as to minimise the earliness and tardiness penalties. This paper proposes a technique to insert the idle time as suitable as possible while meeting due date. The proposed algorithm minimises the penalty, through the insertion of the idle time, up to the point where no further minimisation of the objective function is achieved. The set of upper and lower bounds on the objective function value is presented for the randomly generated problem set. To prove the effectiveness of the algorithm, 400 sets of different sizes ranging from 15 jobs to 100 jobs are solved. The proposed method can be used as a benchmark for future approaches in the area of specific due date scheduling.