A constraint programming-based approach to the crew scheduling problem of the Taipei mass rapid transit system

This paper addresses the crew scheduling problem for a mass rapid transit (MRT) system. The problem is to find a minimum number of duties to cover all tasks while satisfying all the hard and soft scheduling rules. Such rules are complicated in real-world operations and difficult to follow through optimization methods alone. In this paper, we propose a constraint programming (CP)-based approach to solve the problem. The approach involves a CP model for duty generation, a set covering problem model for duty optimization, and alternative ways to identify the final solution in different situations. We applied the proposed CP-based approach to solve a case problem for the Taipei MRT. Case application results using real-world data showed that our approach is capable of reducing the number of daily duties from 58 to 55 and achieving a 5.2 % savings in labor costs. We also incorporated the soft rule considerations into the CP model in order to generate alternative optimum solutions that would improve the workload balance. The coefficient of variation of the work time distribution improves significantly, falling from 21 % to approximately 5 %. Given the CP model’s comprehensive coverage of various scheduling rules, our proposed approach and models would also be applicable to other MRT systems.     

Evolutionary search for difficult problem instances to support the design of job shop dispatching rules

Dispatching rules are simple scheduling heuristics that are widely applied in industrial practice. Their popularity can be attributed to their ability to flexibly react to shop floor disruptions that are prevalent in many real-world manufacturing environments. However, it is a challenging and time-consuming task to design local, decentralised dispatching rules that result in a good global performance of a complex shop.An evolutionary algorithm is developed to generate job shop problem instances for which an examined dispatching rule fails to achieve a good solution due to a single suboptimal decision. These instances can be easily analysed to reveal limitations of that rule which helps with the design of better rules. The method is applied to a job shop problem from the literature, resulting in new best dispatching rules for the mean flow time measure.     

Soft computing optimization methods applied to logistic processes

This paper discusses the methodologies that can be used to optimize a logistic process of a supply chain described as a scheduling problem. First, a model of the system based on a real-world example is presented. Then, a new objective function called Global Expected Lateness is proposed, in order to describe multiple optimization criteria. Finally, three different optimization methodologies are proposed: a classical dispatching rule, and two soft computing techniques, Genetic Algorithms (GA) and Ant Colony Optimization (ACO). These methodologies are compared to the dispatching policy in the real-world example. The results show that dispatching heuristics are outperformed by the GA and ACO meta-heuristics. Further, it is shown that GA and ACO provide statistically identical scheduling solutions and from the optimization performance point of view, it is equivalent to use any of the meta-heuristics.     

A two-phase method for selecting IMRT treatment beam angles: Branch-and-Prune and local neighborhood search

This paper presents a new two-phase solution approach to the beam angle and fluence map optimization problem in Intensity Modulated Radiation Therapy (IMRT) planning. We introduce Branch-and-Prune (B&P) to generate a robust feasible solution in the first phase. A local neighborhood search algorithm is developed to find a local optimal solution from the Phase I starting point in the second phase. The goal of the first phase is to generate a clinically acceptable feasible solution in a fast manner based on a Branch-and-Bound tree. In this approach, a substantially reduced search tree is iteratively constructed. In each iteration, a merit score based branching rule is used to select a pool of promising child nodes. Then pruning rules are applied to select one child node as the branching node for the next iteration. The algorithm terminates when we obtain a desired number of angles in the current node. Although Phase I generates quality feasible solutions, it does not guarantee optimality. Therefore, the second phase is designed to converge Phase I starting solutions to local optimality. Our methods are tested on two sets of real patient data. Results show that not only can B&P alone generate clinically acceptable solutions, but the two-phase method consistently generates local optimal solutions, some of which are shown to be globally optimal.     

A new dispatching rule based genetic algorithm for the multi-objective job shop problem

Hyper-heuristics or “methodologies to choose heuristics” are becoming increasingly popular given their suitability to solve hard real world combinatorial optimisation problems. Their distinguishing feature is that they operate in the space of heuristics or heuristic components rather than in the solution space. In Dispatching Rule Based Genetic Algorithms (DRGA) solutions are represented as sequences of dispatching rules which are called one at a time and used to sequence a number of operations onto machines. The number of operations that each dispatching rule in the sequence handles is a parameter to which DRGA is notoriously sensitive. This paper proposes a new hybrid DRGA which searches simultaneously for the best sequence of dispatching rules and the number of operations to be handled by each dispatching rule. The investigated DRGA uses the selection mechanism of NSGA-II when handling multi-objective problems.     

Nested partitions for the large-scale extended job shop scheduling problem

This paper addresses the large-scale extended job shop scheduling problem while considering the bill of material and the working shifts constraints. We propose two approaches for the problem. One is based on dispatching rules (DR), and the other is an application of the Nested Partitions (NP) Framework. A sampling approach for the exact feasible subregion is developed to complete the NP method. Furthermore, to efficiently search each subregion, a weighted sampling approach is also presented. Computational experiments show that the NP method with weighted sampling can find good solutions for most large-scale extended job shop scheduling problems.     

A genetic algorithms simulation approach for the multi-attribute combinatorial dispatching decision problem

This paper presents a genetic algorithms (GA) simulation approach in solving a multi-attribute combinatorial dispatching (MACD) decision problem in a flow shop with multiple processors (FSMP) environment. The simulation is capable of modeling a non-linear and stochastic problem. GA are one of the commonly used metaheuristics and are a proven tool for solving complex optimization problems. The proposed GA simulation approach addresses a complex MACD problem. Its solution quality is illustrated by a case study from a multi-layer ceramic capacitor (MLCC) manufacturing plant. Because GA search results are often sensitive to the search parameters, this research optimized the GA parameters by using regression analysis. Empirical results showed that the GA simulation approach outperformed several commonly used dispatching rules. The improvements are ranging from 33% to 61%. On the other hand, the increased shop-floor-control complexity may hinder the implementation of the system. Finally, future research directions are discussed.     

A Simulation and Learning Technique for Generating Knowledge about Manufacturing Systems Behavior

One of the most important difficulties when developing knowledge based systems in manufacturing scheduling or control, is finding the required knowledge. We address here the problem of acquiring knowledge about the behavior of manufacturing systems. Learning algorithms are proposed to generate, from simulation experiments, a set of production rules. This set may be considered as a simulation meta-model, and may be used either directly by the shop manager, or inserted into a knowledge base. This approach is illustrated by the use of the learning program GENREG. It generates rules related to the behavior of a simplified flow shop when different dispatching rules are applied.     

A Globally Convergent Algorithm for a PDE-Constrained Optimization Problem Arising in Electrical Impedance Tomography

We study the convergence properties of an algorithm for the inverse problem of electrical impedance tomography, which can be reduced to a partial differential equation (PDE) constrained optimization problem. The direct problem consists of the potential equation div(??u) = 0 in a circle, with Neumann condition describing the behavior of the electrostatic potential in a medium with conductivity given by the function ?(x, y). We suppose that at each time a current ψ _i is applied to the boundary of the circle (Neumann's data), and that it is possible to measure the corresponding potential ? _i (Dirichlet data). The inverse problem is to find ?(x, y) given a finite number of Cauchy pairs measurements (? _i , ψ _i ), i = 1,…, N. The problem is formulated as a least squares problem, and the developed algorithm solves the continuous problem using descent iterations in its corresponding finite element approximations. Wolfe's conditions are used to ensure the global convergence of the optimization algorithm for the continuous problem. Although exact data are assumed, measurement errors in data and regularization methods shall be considered in a future work.     

Approximation guarantees of algorithms for fractional optimization problems arising in dispatching rules for INDS problems

In this paper, we provide approximation guarantees of algorithms for the fractional optimization problems arising in the dispatching rules from recent literature for Integrated Network Design and Scheduling problems. These fractional optimization problem are proved to be NP-hard. The approximation guarantees are based both on the number of arcs in the network and on the number of machines in the scheduling environment. We further demonstrate, by example, the tightness of the factors for these approximation algorithms.     

Finding preferred subsets of Pareto optimal solutions

Multi-objective optimization algorithms can generate large sets of Pareto optimal (non-dominated) solutions. Identifying the best solutions across a very large number of Pareto optimal solutions can be a challenge. Therefore it is useful for the decision-maker to be able to obtain a small set of preferred Pareto optimal solutions. This paper analyzes a discrete optimization problem introduced to obtain optimal subsets of solutions from large sets of Pareto optimal solutions. This discrete optimization problem is proven to be NP-hard. Two exact algorithms and five heuristics are presented to address this problem. Five test problems are used to compare the performances of these algorithms and heuristics. The results suggest that preferred subset of Pareto optimal solutions can be efficiently obtained using the heuristics, while for smaller problems, exact algorithms can be applied.     

Sensitivity Analysis of Merit Function in Solving Nonlinear Equations by Optimization

To solve nonlinear equations by an optimization method, scaling is very important. Two types of poor scaling where: (a) the variables differ greatly in magnitude; (b) the merit function of system is highly sensitive to small changes in certain variables and relatively insensitive to changes in other variables. If poor scaling is ignored, the algorithm may produce solutions with poor quality. To solve (a), we can change units of variables. A numerical solution of the nonlinear equations produced by the finite volume method in the forced convective heat transfer of a nanofluid, as a case study, indicates that the poor scaling (b) is solved by using the Euclidean norm of columns of the Jacobian matrix as scaling data, while some researchers proposed diagonal elements of the Hessian matrix as scaling data.     

A dispatching algorithm for parallel machines with rework processes

This paper presents a parallel machine scheduling problem with rework probabilities, due-dates and sequence-dependent setup times. It is assumed that rework probability for each job on a machine can be given through historical data acquisition. Since the problem is NP-hard in the strong sense, a heuristic algorithm is presented, which finds good solutions. The dispatching algorithm named MRPD (minimum rework probability with due-dates) is proposed in this paper focusing on the rework processes. The performance of MRPD is measured by the six diagnostic indicators: total tardiness, maximum lateness, mean flow-time, mean lateness, the number of reworks and the number of tardy jobs. A large number of test problems are randomly generated to evaluate the performance of the proposed algorithm. Computational results show that the proposed algorithm is significantly superior to existing dispatching algorithms for the test problems.     

Experimental investigation of real-time scheduling in flexible manufacturing systems

This paper presents a new two-phase (TP) approximate method for real-time scheduling in a flexible manufacturing system (FMS). This method combines a reduced enumeration schedule generation algorithm with a 0–1 optimization algorithm. In order to make the combined algorithm practicable, heuristic rules are introduced for the selection of jobs to be scheduled. The relative performance of the TP method vis-a-vis conventional heuristic dispatching rules such as SPT, LPT, FCFS, MWKR, and LWKR is investigated using combined process-interaction/discrete-event simulation models. An efficient experimental procedure is designed and implemented using these models, and the statistical analysis of the results is presented. For the particular case investigated, the conclusions are very encouraging. In terms of mean flow time, the TP method performs significantly better than any other tested heuristic dispatching rules. Also, the experimental results show that using global information significantly improves the FMS performance.     

Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming

In exact arithmetic, the simplex method applied to a particular linear programming problem instance with real data either shows that it is infeasible, shows that its dual is infeasible, or generates optimal solutions to both problems. Most interior-point methods, on the other hand, do not provide such clear-cut information. If the primal and dual problems have bounded nonempty sets of optimal solutions, they usually generate a sequence of primal or primaldual iterates that approach feasibility and optimality. But if the primal or dual instance is infeasible, most methods give less precise diagnostics. There are methods with finite convergence to an exact solution even with real data. Unfortunately, bounds on the required number of iterations for such methods applied to instances with real data are very hard to calculate and often quite large. Our concern is with obtaining information from inexact solutions after a moderate number of iterations. We provide general tools (extensions of the Farkas lemma) for concluding that a problem or its dual is likely (in a certain well-defined sense) to be infeasible, and apply them to develop stopping rules for a homogeneous self-dual algorithm and for a generic infeasible-interior-point method for linear programming. These rules allow precise conclusions to be drawn about the linear programming problem and its dual: either near-optimal solutions are produced, or we obtain certificates that all optimal solutions, or all feasible solutions to the primal or dual, must have large norm. Our rules thus allow more definitive interpretation of the output of such an algorithm than previous termination criteria. We give bounds on the number of iterations required before these rules apply. Our tools may also be useful for other iterative methods for linear programming. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

A mixed integer programming model for scheduling orders in a steel mill

The problem of scheduling orders at each facility of a large integrated steel mill is considered. Orders are received randomly, and delivery dates are established immediately. Each order is filled by converting raw materials into a finished saleable steel product by a fixed sequence of processes. The application of a deterministic mixed integer linear programming model to the order scheduling problem is given. One important criterion permitted by the model is to process the orders in a sequence which minimizes the total tardiness from promised delivery for all orders; alternative criteria are also possible. Most practical constraints which arise in steelmaking can be considered within the formulation. In particular, sequencing and resource availability constraints are handled easily. The order scheduling model given here contains many variables and constraints, resulting in computational difficulties. A decomposition algorithm is devised for solving the model. The algorithm is a special case of Benders partitioning. Computational experience is reported for a large-scale problem involving scheduling 102 orders through ten facilities over a six-week period. The exact solution to the large-scale problem is compared with schedules determined by several heuristic dispatching rules. The dispatching rules took into consideration such things as due date, processing time, and tardiness penalties. None of the dispatching rules found the optimal solution.     

A parametric simplex algorithm for linear vector optimization problems

In this paper, a parametric simplex algorithm for solving linear vector optimization problems (LVOPs) is presented. This algorithm can be seen as a variant of the multi-objective simplex (the Evans–Steuer) algorithm (Math Program 5(1):54–72, 1973). Different from it, the proposed algorithm works in the parameter space and does not aim to find the set of all efficient solutions. Instead, it finds a solution in the sense of Löhne (Vector optimization with infimum and supremum. Springer, Berlin, 2011), that is, it finds a subset of efficient solutions that allows to generate the whole efficient frontier. In that sense, it can also be seen as a generalization of the parametric self-dual simplex algorithm, which originally is designed for solving single objective linear optimization problems, and is modified to solve two objective bounded LVOPs with the positive orthant as the ordering cone in Ruszczyński and Vanderbei (Econometrica 71(4):1287–1297, 2003). The algorithm proposed here works for any dimension, any solid pointed polyhedral ordering cone C and for bounded as well as unbounded problems. Numerical results are provided to compare the proposed algorithm with an objective space based LVOP algorithm [Benson’s algorithm in Hamel et al. (J Global Optim 59(4):811–836, 2014)], that also provides a solution in the sense of Löhne (2011), and with the Evans–Steuer algorithm (1973). The results show that for non-degenerate problems the proposed algorithm outperforms Benson’s algorithm and is on par with the Evans–Steuer algorithm. For highly degenerate problems Benson’s algorithm (Hamel et al. 2014) outperforms the simplex-type algorithms; however, the parametric simplex algorithm is for these problems computationally much more efficient than the Evans–Steuer algorithm.     

Informationally optimal correlation

This papers studies an optimization problem under entropy constraints arising from repeated games with signals. We provide general properties of solutions and a full characterization of optimal solutions for 2 × 2 sets of actions. As an application we compute the minmax values of some repeated games with signals.     

Reformulation and a Lagrangian heuristic for lot sizing problem on parallel machines

We consider the capacitated lot sizing problem with multiple items, setup time and unrelated parallel machines. The aim of the article is to develop a Lagrangian heuristic to obtain good solutions to this problem and good lower bounds to certify the quality of solutions. Based on a strong reformulation of the problem as a shortest path problem, the Lagrangian relaxation is applied to the demand constraints (flow constraint) and the relaxed problem is decomposed per period and per machine. The subgradient optimization method is used to update the Lagrangian multipliers. A primal heuristic, based on transfers of production, is designed to generate feasible solutions (upper bounds). Computational results using data from the literature are presented and show that our method is efficient, produces lower bounds of good quality and competitive upper bounds, when compared with the bounds produced by another method from the literature and by high-performance MIP software.     

Solving the dynamic ambulance relocation and dispatching problem using approximate dynamic programming

Emergency service providers are supposed to locate ambulances such that in case of emergency patients can be reached in a time-efficient manner. Two fundamental decisions and choices need to be made real-time. First of all immediately after a request emerges an appropriate vehicle needs to be dispatched and send to the requests’ site. After having served a request the vehicle needs to be relocated to its next waiting location. We are going to propose a model and solve the underlying optimization problem using approximate dynamic programming (ADP), an emerging and powerful tool for solving stochastic and dynamic problems typically arising in the field of operations research. Empirical tests based on real data from the city of Vienna indicate that by deviating from the classical dispatching rules the average response time can be decreased from 4.60 to 4.01 minutes, which corresponds to an improvement of 12.89%. Furthermore we are going to show that it is essential to consider time-dependent information such as travel times and changes with respect to the request volume explicitly. Ignoring the current time and its consequences thereafter during the stage of modeling and optimization leads to suboptimal decisions.