Abstract:

Classically, in operations research, one seeks to solve a problem whose set of parameters is known with certainty. However, this is rarely the case in practice. For example, for a problem in which we want to schedule a set of tasks, it is possible that one of the tasks falls behind, making the rest of the initially calculated schedule infeasible. Several approaches exist to deal with those uncertainties, and among them, we are particularly interested in robust optimization, where the uncertainties are modeled by scenarios, and where we try to compute a solution that degrades as little as possible in its worst case scenario. Nevertheless, those approaches tend to produce solutions that are too pessimistic. To overcome this, we propose a decision analysis model, based on decision trees, which proposes to a decision maker alternative solutions that adapt to the scenario as it unfolds, according to the information available to the decision maker. We have applied those decision trees to aircraft assembly line scheduling problems, which can be viewed as a multi-mode project scheduling problem, on reference instances as well as on real industrial instances, and have shown the interest of our model. We then propose to improve the solution of some robust optimization problems with a variant of a classical method, the Adversarial Benders method. This method relies in part on the approximation of the set of scenarios by a subset, initially empty, to which scenarios are added one by one. In our variant, scenarios are added in small groups by being represented in what is called a budget graph. We show that the method of selecting the scenario group is critical, and apply our variant on a production planning problem.