Modelling Uncertainty in Flow Shop Scheduling Problem Using Interval Arithmetic

Scheduling of jobs is an important problem in operational planning, network optimization or airplane landing. A standard scheduling model assumes that jobs processing times and other production process parameters are crisp. In practice, however, job processing times are often subject to uncertainty due to machine micro-stoppages, breakdowns unexpected service. Uncertainty may result as well from unexpected arrivals of new jobs with high priorities, late arrivals of raw materials, varying setup times, release dates and due dates, etc. The most widespread approach to model uncertain processing times is to use fuzzy numbers, but often the only available information about processing times or job parameters are their lower and upper bounds. In such case, processing times can be conveniently modelled as intervals. In this paper we consider a permutation flowshop scheduling problem with processing times given as interval numbers. Two metaheuristics are used to solve the problem thus determined: tabu search and genetic algorithm. The methods are compared using several instances of the flowshop scheduling problems based on well-known Taillard’s benchmarks.