Single machine scheduling with small operator-non-availability periods

For an industrial application in the chemical industry, we were confronted with the planning of experiments, where human intervention of a chemist is required to handle the starting and termination of each of the experiments. This gives rise to a new type of scheduling problem, namely problems of finding schedules with time periods when the tasks can neither start nor finish. We consider in this paper the natural case of small periods where the duration of the periods is smaller than any processing time. This assumption corresponds to our chemical experiments lasting several days, whereas the operator unavailability periods are typically single days or week-ends. These problems are analyzed on a single machine with the makespan as criterion.     

Cross‐comparison of convergence algorithms to solve trip‐based dynamic traffic assignment problems

Solving a dynamic traffic assignment problem in a transportation network is a computational challenge. This study first reviews the different algorithms in the literature used to numerically calculate the user equilibrium (UE) related to dynamic network loading. Most of them are based on iterative methods to solve a fixed‐point problem. Two elements must be computed: the path set and the optimal path flow distribution between all origin–destination pairs. In a generic framework, these two steps are referred to as the outer and the inner loops, respectively. The goal of this study is to assess the computational performance of the inner loop methods that calculate the path flow distribution for different network settings (mainly network size and demand levels). Several improvements are also proposed to speed up convergence: four new swapping algorithms and two new methods for the step size initialization used in each descent iteration. All these extensions significantly reduce the number of iterations to obtain a good convergence rate and drastically speed up the overall simulations. The results show that the performance of different components of the solution algorithm is sensitive to the network size and saturation. Finally, the best algorithms and settings are identified for all network sizes with particular attention being given to the largest scale.     

Simulation‐based dynamic traffic assignment: Meta‐heuristic solution methods with parallel computing

The aim of this study is to solve the large‐scale dynamic traffic assignment (DTA) model using a simulation‐based framework, which is computationally a challenging problem. Many studies have been performed on developing an efficient algorithm to solve DTA. Most of the existing algorithms are based on path‐swapping descent direction methods. From the computational standpoint, the main drawback of these methods is that they cannot be parallelized. This is because the existing algorithms need to know the results of the last iteration to determine the next best path flow for the next iteration. Thus, their performance depends on the single initial or intermediate solution, which means they exploit a solution that satisfies the equilibrium conditions more than explore the solution space for the optimal solution. More specifically, the goal of this study is to overcome the drawbacks of serial algorithms by using meta‐heuristic algorithms known to be parallelizable and that have never been applied to the simulation‐based DTA problem. This study proposes two new solution methods: a new extension of the simulated annealing and an adapted genetic algorithm. With parallel simulation, the algorithm runs more simulations in comparison with existing methods, but the algorithm explores the solution space better and therefore obtains better solutions in terms of closeness to the optimal solution and computation time compared to classical methods.     

Scheduling of coupled tasks and one-machine no-wait robotic cells

Coupled task scheduling problems have been known for more than 25 years. Several complexity results have been established in the meantime, but the status of the identical task case remains still unsettled. We describe a new class of equivalent one-machine no-wait robotic cell problems. It turns out that scheduling of identical coupled tasks corresponds to the production of a single part type in the robotic cell. We shall describe new algorithmic procedures to solve this robotic cell problem, allowing lower and upper bounds on the production time and discussing in particular cyclic production plans.     

Optimal sub-networks in traffic assignment problem and the Braess paradox

This paper is related to the Braess paradox. For a given transportation network, we are interested in the origin-destination (OD) travel costs in its sub-networks. Speaking about the performance of a network in terms of its equilibrium travel costs, we try to select the best sub-network of the original one. In a one OD pair network, by removing arcs, the equilibrium travel cost can decrease. Thus we ask for a sub-network for which the travel cost at equilibrium is minimum. In the case of multiple OD pairs, a multi-criteria comparison concept (Pareto optimality) is used to compare equilibria in sub-networks. The problem is formulated as an optimization problem. Only the fixed demand case is dealt with.