A learning based matheuristic to solve the two machine flowshop scheduling problem with sum of completion times
Résumé
Consider the problem where $n$ jobs have to be scheduled on two machines organized in a flowshop setting. Each job $j$ is defined by a \emph{processing time} $p_{j,i}$ on machine $i=1,2$ and has to be processed first on machine 1 and next on machine 2. Each machine can only process one job at a time and preemption is not allowed. We restrict the search for a solution to the set of permutation schedules. Therefore, the goal is to find a schedule $s$ (permutation) that minimizes the total completion time $\sum_j C_j(s)$ with $C_j(s)$ the completion time of job $j$ in schedule $s$. When there is no ambiguity, we omit the reference to schedule $s$ when referring to completion times. Following the standard three-field notation in scheduling theory, this problem is referred to as
$F2||\sum_j C_j$ and is strongly $\cal NP$-hard \cite{GJS76}.\\
The $F2||\sum_j C_j$ problem is a challenging problem which has been studied for a long time from both exact and heuristic point of views. In this work, we don't consider exact approaches. Along the years, several heuristic algorithms have been proposed and, to the best of our knowledge, the most efficient one is a matheuristic proposed in \cite{DAS04}. Matheuristics are local search algorithms which explore the neighborhood of an incumbent solution by solving a mathematical programming formulation of the problem. In this work we propose the developpment of a learning based predictor to improve the matheuristic proposed in \cite{DAS04}.
Origine : Fichiers produits par l'(les) auteur(s)