Tardiness Minimisation for Job Shop Scheduling with Interval Uncertainty

Abstract

This paper considers the interval job shop scheduling problem, a variant of the deterministic problem where task durations and due dates are uncertain and modelled as intervals. With the objective of minimising the total tardiness with respect to due dates, we propose a genetic algorithm. Experimental results are reported to assess its behaviour and compare it with the state-of-the-art algorithms, showing its competitiveness. Additional results in terms of solution robustness are given to illustrate the relevance of the interval ranking method used to compare schedules as well as the benefits of taking uncertainty into account during the search process.