The Cyclic Job Shop Problem with uncertain processing times

Idir Hamaz (1) , Laurent Houssin (1) , Sonia Cafieri (2)

1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
2 ENAC - Ecole Nationale de l'Aviation Civile

Most models for scheduling problems assume deterministic parameters. In contrast, real world scheduling problems are often subject to many sources of uncertainty, for example activities duration can decrease or increase, machines can break down, new activities can be incorporated, etc. In this paper, we focus on scheduling problems that are cyclic and where activity durations are affected by uncertainty. Indeed, the best solution for a deterministic problem can quickly become the worst one in the presence of uncertainties. In this paper, we consider the Cyclic Job Shop Problem (CJSP) where processing times are affected by uncertainty. Several studies were conducted on the deterministic CJSP. The CJSP with identical parts is studied in (Roundy, R. 1992). The author shows that the problem is NP-hard and designs a branch and bound algorithm to solve the problem. Hanen (1994) investigates the general CJSP and presents a branch and bound procedure to tackle the problem. A general framework for modeling and solving cyclic scheduling problems is presented in (Brucker, P. and Kampmeyer, T. 2008). The authors present different models for cyclic versions of the job shop problem. However, a few works consider cyclic scheduling problems under uncertainty. Che, A. et. al. (2015) investigate the cyclic hoist scheduling problem with processing time window constraints where the hoist transportation times are uncertain. The authors define a robustness measure for cyclic hoist schedule and a bi-objective mixed integer linear program to optimize the cycle time and the robustness. In order to deal with uncertainty, we use a robust optimization approach. We model the uncertain parameters by using the idea of uncertainty set proposed by Bertsimas and Sim (2004). Each task duration belongs to an interval, and the number of parameters that can deviate from their nominal values is bounded by a positive number called budget of uncertainty. This parameter allows us to control the degree of conservatism of the resulting schedule. Finally, we propose a branch and bound procedure that computes the minimum cycle time for the robust CJSP such that, for each scenario in the uncertainty set, there exists a feasible cyclic schedule.

Mots clés: Cyclic scheduling; budgeted uncertainty set; robust optimization

Domaines: Recherche opérationnelle [math.OC]; Mathématique discrète [cs.DM]

Idir Hamaz, Laurent Houssin, Sonia Cafieri. The Cyclic Job Shop Problem with uncertain processing times. 16th International Conference on Project Management and Scheduling (PMS 2018), Apr 2018, Rome, Italy. ⟨hal-01876486⟩