In this work, we focus on a non-preemptive unrelated parallel machines scheduling problem with a common server and job-sequence dependent setup times. This problem arises when planning the production of some mechanical parts of automobile, hydraulic and electrical sectors. It's well known to be NP-Hard. We first propose new mixed integer linear programming formulations for the problem. We then compare them with the only state-of-the-art formulation for the same problem. Based on these results, we devise a Branch-and-Cut algorithm along with computational results are presented to evaluate the performance of our approach. Moreover, we provide a warm starting algorithm for the problem, and further show its influence on boosting the Branch-and-Cut algorithm.

In this paper, we study the Constrained-Routing and Spectrum Assignment (C-RSA) problem. Consider an undirected, loopless, and connected graph${G}$. Let$\mathbb{S}$be an optical spectrum of available contiguous frequency slots, and${K}$be a set of traffic demands. The C-RSA is to assign for each demand${k\,\in \,K}$a path in${G}$between its origin-destination nodes, and an interval of contiguous frequency slots in$\mathbb{S}$while respecting some technological constraints, and optimizing some linear objective function. First, we propose an extended integer linear programming formulation for the C-RSA. A column generation algorithm is developed to solve its linear relaxation. We also describe several valid inequalities for the polytope associated with this formulation, and address the related separation problems. Using these results, we derive a Branch-and-Cut-and-Price algorithm, along with computational results are presented using large-scale instances.

The routing and spectrum assignment problem is an NP-hard problem that receives increasing attention during the last years.Existing integer linear programming models for the problem are either very complex and suffer from tractability issues or are simplified and incomplete so that they can optimize only some objective functions.The majority of models uses edgepath formulations where variables are associated with all possible routing paths so that the number of variables grows exponentially with the size of the instance.An alternative is to use edgenode formulations that allow to devise compact models where the number of variables grows only polynomially with the size of the instance.However, all known edge-node formulations are incomplete as their feasible region is a superset of all feasible solutions of the problem and can, thus, handle only some objective functions.Our contribution is to provide the first complete edge-node formulation for the routing and spectrum assignment problem which leads to a tractable integer linear programming model.Indeed, computational results show that our complete model is competitive with incomplete models as we can solve instances of the RSA problem larger than instances known in the literature to optimality within reasonable time and w.r.t.several objective functions.We further devise some directions of future research.