SCHEDULING OF JOBS WITH DETERIORATING PROCESSING TIMES DEPENDING ON DUE DATES

ABSTRACT This paper focuses on a scheduling problem that arises when job processing times are variable and subject to change based on due dates. The objective is to minimize the makespan on a single machine, while ensuring that jobs are completed independently and without interruption. This problem is challenging due to the possibility of a job’s processing time deteriorating over time. We have developed two mixed integer programming models to obtain optimal solutions, but due to the NP-hardness of this problem, we recommend using heuristics and metaheuristics (genetic algorithm and simulated annealing) as well. To validate our approach, we conducted computational experiments using randomly generated test instances. Our findings indicate that the improved second model can produce better solutions for up to 40 jobs within a one hour time frame. Furthermore, the genetic algorithm performs comparably better than other heuristics and simulated annealing for larger instances.