A new robust approach for a production scheduling and delivery routing problem

International audienceIn a supply chain, two essential elements are the production and the distribution. These two problems used to be solved separately, but it it well known that considering them jointly may lead to a global optimization of the supply chain performances. In this paper, we incorporate the delivery plan of a vehicle into a single machine scheduling problem, representing a single manufacturing facility. We consider the simplified case where there is only one vehicle available to serve the customers, with infinite capacity. However, we assume that the data are known with uncertainty. The objective is to find a schedule and a delivery plan so that a robustness criteria is minimized, under a scenario-based uncertainty modeling. In contrast with standard robust optimization approaches for scheduling, we do not propose a single complete solution to the problem that has to be feasible w.r.t. all scenarios and minimizes a worst-case criterion over the scenarios. Instead, we adopt the recoverable robustness framework that considers first-stage decisions and second-stage recovery options. We propose for the first-stage a set of solutions by using the concept of groups of permutable jobs. At second stage, a greedy and online recovery algorithm exploits the revealed information about the jobs available to be scheduled or to be delivered at decision time. We propose two tabu search algorithms, one based on the standard robust optimization scheme and one based on the new approach. We compare the two robust heuristics on a set of randomly generated problem instances