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

Authors: A.N. Senthilvel; S. Umamaheswari; C. Arumugam

Addresses: Department of Computer Science and Engineering, Coimbatore Institute of Technology, Coimbatore, Tamilnadu, India ' Department of Electronics and Communication Engineering, Coimbatore Institute of Technology, Coimbatore, Tamilnadu, India ' Department of Mechanical Engineering, Coimbatore Institute of Technology, Coimbatore, Tamilnadu, India

Abstract: 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.

Keywords: scheduling algorithm; job sequencing; NP class; heuristic approach; idle time; global optimisation.

DOI: 10.1504/IJOR.2021.115416

International Journal of Operational Research, 2021 Vol.41 No.1, pp.114 - 134

Accepted: 29 Dec 2017
Published online: 02 Jun 2021 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article