Stochastic single machine scheduling problem as a multi-stage dynamic random decision process

In this work, we study a stochastic single machine scheduling problem in which the features of learning
effect on processing times, sequence-dependent setup times, and machine configuration selection are
considered simultaneously. More precisely, the machine works under a set of configurations and requires
stochastic sequence-dependent setup times to switch from one configuration to another. Also, the
stochastic processing time of a job is a function of its position and the machine configuration. The
objective is to find the sequence of jobs and choose a configuration to process each job to minimize the
makespan. We first show that the proposed problem can be formulated through two-stage and multi-stage
Stochastic Programming models, which are challenging from the computational point of view. Then, by
looking at the problem as a multi-stage dynamic random decision process, a new deterministic
approximation-based formulation is developed. The method first derives a mixed-integer non-linear model
based on the concept of accessibility to all possible and available alternatives at each stage of the decision-making process. Then, to efficiently solve the problem, a new accessibility measure is defined to convert
the model into the search of a shortest path throughout the stages. Extensive computational experiments are
carried out on various sets of instances. We discuss and compare the results found by the resolution of
plain stochastic models with those obtained by the deterministic approximation approach. Our
approximation shows excellent performances both in terms of solution accuracy and computational time.