A constraint programming-based solution approach for medical resident scheduling problems

Persistent calls come from within the graduate medical education community and from external sources for regulating the resident duty hours in order to meet the obligations about the quality of resident education, the well-being of residents themselves, and the quality of patient care services. The report of the Accreditation Council for Graduate Medical Education (ACGME) proposes common program requirements for resident hours. In this paper, we first develop a mixed-integer programming model for scheduling residents’ duty hours considering the on-call night, day-off, rest period, and total work-hour ACGME regulations as well as the demand coverage requirements of the residency program. Subsequently, we propose a column generation model that consists of a master problem and an auxiliary problem. The master problem finds a configuration of individual schedules that minimizes the sum of deviations from the desired service levels for the day and night periods. The formulation of this problem is possible by representing the feasible schedules using column variables, whereas the auxiliary problem finds the whole set of feasible schedules using constraint programming. The proposed approach has been tested on a series of problems using real data obtained from a hospital. The results indicate that high-quality schedules can be obtained within a few seconds.     

Solving a real-life, large-scale energy management problem

This paper introduces a three-phase hybrid heuristic for a large-scale energy management and maintenance scheduling problem. The problem is to schedule maintenance periods and refueling amounts for nuclear power plants with a time horizon of up to five years, and handling a number of scenarios for future demand and prices. The goal is to minimize the expected total production cost. The first phase of the heuristic solves a constraint programming model of a simplified version of the problem, the second performs a local search, and the third handles overproduction in a greedy fashion. This work was initiated in the context of the ROADEF/EURO Challenge 2010. In the concluding phase of the competition, our team ranked second in the junior category and sixth overall. After correcting a small implementation bug in the program that was submitted for final evaluation, our solver ranks first in the overall results from the competition.     

A portfolio approach to multi-product newsboy problem with budget constraint

This paper investigates a portfolio approach to multi-product newsboy problem with budget constraint, in which the procurement strategy for each newsboy product is designed as portfolio contract. A portfolio contract consists of a fixed-price contract and an option contract. We model the problem as a profit-maximization model, and propose an efficient solution procedure after investigating the structural properties of the model. We conduct numerical studies to show the efficiency of the proposed solution procedure, and to compare three models with different procurement contracts, i.e., fixed-price contract, option contract, and portfolio contract. Numerical results are shown to demonstrate the advantage of the portfolio model, and sensitivity analysis is provided for obtaining some managerial insights.     

A hybrid constraint programming approach to a wood procurement problem with bucking decisions

In this article, we present a wood procurement problem that arises in Eastern Canada. We solve a multi-period wood supply planning problem, while taking into account bucking decisions. Furthermore, we present a new form of flexibility which allows the harvesting capacity to change from one time period to another. We study the impact of such flexibility upon the harvesting cost. We assess the performance of the problem by comparing it with a variant where the harvesting capacity is fixed during sites’ harvesting. To address this problem, we develop a hybrid approach based on both constraint and mathematical programming. In the first phase, we propose a constraint programming model dealing with forest sites harvesting and bucking problems. The result of this model is used as part of an initial solution for the whole problem formulated as a mixed integer model. We test the two versions of the problem on a set of different demand instances and we compare their results.     

A linguistic-engineering approach to large-scale requirements management

For large software companies, the sheer number of textual requirements presents specific challenges. To find market opportunities, organizations must continuously elicit new requirements and reevaluate old ones as market needs evolve. Developing large, complex software products aimed at broad markets involves identifying and maintaining the link between product requirements and the massive inflow of customers' wishes. Automating this support through linguistic engineering could save considerable time and improve software quality.     

A constraint programming approach to the Chinese postman problem with time windows

The Chinese postman problem with time windows (CPPTW) is modelled as a constraint programme and results are reported for a set of test problems with up to 69 edges. Two different formulations are proposed. The first formulation approaches the problem directly and the second transforms the problem to an equivalent vehicle routing problem with time windows. The results demonstrate that optimal solutions can be obtained quickly when the time windows are tight. However, the results also show that as the time windows are made wider and the number of feasible solutions increases, these constraint programming formulations take significantly longer to find a provably optimal solution. The results also demonstrate how the size and density of the graph affects the computing time needed to find an optimal solution.     

A constraint satisfaction problem algorithm for large-scale multi-panel composite structures

Structural and Multidisciplinary Optimization - This paper proposes a constraint satisfaction problem algorithm based on implicit decision trees and dynamic programming for the design of multiple...     

A constraint programming approach to the multiple-venue,sport-scheduling problem

In this paper, we consider the problem of scheduling sports competitions over several venues which are not associated with any of the competitors. A two-phase, constraint programming approach is developed, first identifying a solution that designates the participants and schedules each of the competitions, then assigning each competitor as the “home” or the “away” team. Computational experiments are conducted and the results are compared with an integer goal programming approach. The constraint programming approach achieves optimal solutions for problems with up to sixteen teams, and near-optimal solutions for problems with up to thirty teams.     

Production management as a constraint satisfaction problem

Production management problems can be quite straightforwardly presented as constraint satisfaction problems, where values for some variables are searched for under a set of constraints. A combination of an operation and a resource is usually interpreted as the variable, and a time window is usually interpreted as the value to be searched for. This convention is challenged. A case is considered where the most appropriate interpretation treats the combination of a resource and a time window as the variable, and an operation as the value. A third possible interpretation is also briefly covered, where the combination of an operation and a time window is the variable, and the resource is the value.     

带实际约束的大规模车辆路径问题建模及求解

针对现有算法不能有效求解卷烟配送过程中, 问题规模大并具有诸多实际约束条件限制这类实际问题, 首先分析实际约束, 建立问题模型; 然后从模型出发设计多阶段算法, 通过地理信息的分级管理实现区域划分, 在降低问题规模的同时消除交通障碍; 采用改进的k 均值聚类法分派线路, 将问题转化为求解小规模旅行商问题; 最后以济南市区的卷烟配送为例, 通过与典型优化算法的比较表明了所提出多阶段算法在实际应用中的优越性.

     

A column generation approach for a school bus routing problem with resource constraints

The Multiple Vehicle Traveling Purchaser Problem describes a school bus routing problem that combines bus stop selection and bus route generation. This problem aims at selecting a set of bus stops from among a group of potential locations to pick up students, and for designing bus routes to visit the selected stops and to carry the students to their school. We address a variation of this problem that considers certain constraints on each bus route, such as bounds on the distances traveled by the students, bounds on the number of visited bus stops, and bounds on the minimum number of students that a vehicle has to pick up.     

A linear programming formulation for an inventory management decision problem with a service constraint

Inventory systems with uncertainty go hand in hand with the determination of a safety stock level. The decision on the safety stock level is based on a performance measure, for example the expected shortage per replenishment period or the probability of a stock-out per replenishment period. The performance measure assumes complete knowledge of the probability distribution during lead time, which might not be available. In case of incomplete information regarding the lead-time distribution of demand, no single figure for the safety stock can de determined in order to satisfy a performance measure. However, an optimisation model may be formulated in order to determine a safety stock level which guarantees the performance measure under the worst case of lead-time demand, of which the distribution is known in an incomplete way. It is shown that this optimisation problem can be formulated as a linear programming problem.     

A branch-and-cut approach for the vehicle routing problem with loading constraints

In this paper we describe a branch-and-cut algorithm for the vehicle routing problem with unloading constraints. The problem is to determine a set of routes with minimum total cost, each route leaving a depot, such that all clients are visited exactly once. Each client has a demand, given by a set of items, that are initially stored in a depot. We consider the versions of the problem with two and tri dimensional parallelepiped items. For each route in a solution, we also need to construct a feasible packing for all the items of the clients in this route. As it would be too expensive to rearrange the vehicle cargo when removing the items of a client, it is important to perform this task without moving the other client items. Such packings are said to satisfy unloading constraints.In this paper we describe a branch-and-cut algorithm that uses several techniques to prune the branch-and-cut enumeration tree. The presented algorithm uses several packing routines with different algorithmic approaches, such as branch-and-bound, constraint programming and metaheuristics. The careful combination of these routines showed that the presented algorithm is competitive, and could obtain optimum solutions within significantly smaller computational times for most of the instances presented in the literature.     

A genetic algorithm approach for a single hoist scheduling problem with time windows constraints

This study considers a cyclic scheduling of hoist movements in electroplating industry. Several jobs have to flow through a production line according to an ordered bath sequence. They firstly enter the line at a loading buffer. Then they will be soaked sequentially in a series of tanks containing specific chemical baths. Finally, they will leave the line at the unloading buffer. The processing time duration of each job in each tank is not constant but confined within a time window bounded by a minimum and a maximum duration. If a job spends less than the minimum duration or more than the maximum duration it is considered defective. Moreover, not only the job operations in the soaking tanks have to be scheduled, but also the transportation of the jobs between tanks has to be considered. The problem now is to find an optimum or near optimum feasible cyclic scheduling such that the hard resource and time-window constraints are respected and the cycle time duration is minimized. A mathematical formulation is proposed for the multi-jobs cyclic hoist scheduling problem with a single transportation resource, and a Genetic Algorithm (GA) approach is presented to solve it. The performance of the proposed algorithm is evaluated with the objective value obtained with a linear programming model, on several literature instances. Computational experiments show the good performance of our GA in terms of solution quality, convergence and computation time.     

Modelling and a segmented dynamic programming-based heuristic approach for the slab stack shuffling problem

This paper studies the slab stack shuffling (SSS) problem in the slab yard, which is a key logistics problem between the continuous casting stage and the hot rolling mill in the steel industry. The problem is to choose appropriate slabs for a sequence of rolling items, from their respective candidate slab sets (families) with a view to reducing the resulting shuffling workload. Although the SSS problem has been investigated by a few researchers, the problem under consideration has several new features. One of them is that the shuffled slab will not return the original stack but remain at the new position. Another requires that every selected slab be taken out in time, which will result in balancing the crane workloads among the storage areas of the slab yard to a degree. In addition, the local similarity of slab families is also considered, the closer the items in the rolling sequence, the more the common slabs between the corresponding families. For the problem, an integer programming model is proposed by considering the above features and requirements. For small-scaled problem, a dynamic programming approach is first constructed to obtain its optimal solution. For the practical scale, due to its intractability, we propose a segmented dynamic programming (SDP)-based heuristic, which partitions the sequence of items into a series of segments, each of which corresponds to a subproblem. The subproblems are solved sequentially using the dynamic programming. And the reassignment strategy of common slabs and the exchange strategy of candidate slabs are designed to improve the heuristic. Two interesting properties of the problem are also derived to speed up the SDP-based heuristic approach. The experiment results show that the heuristic is very close to the optimum in average solution quality for the small-scaled problem, obviously better than the CP Optimizer for the medium scale, and can reduce the crane workload by 10.76% on average for the practical scale.     

A time-optimal problem with recoverability constraint

This paper introduces the concept of recoverability as a design consideration. A simple time-optimal regulator problem is modified to explore the feasibility of imposing a recoverability constraint as an explicit restriction on the system state during control synthesis. The results are summarized as two theorems. Comparative numerical data for both unconstrained and constrained trajectories are presented.     

A new constraint programming approach for the orthogonal packing problem

The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles can be packed in a larger rectangle of fixed size. We propose an exact method for 2OPP, based on a new constraint-based scheduling model. We provide a generalization of energetic reasoning techniques for the problem under investigation. Feasibility tests requiring the solution of subset-sum problems are described. Computational results confirm the efficiency of our method compared to others in the literature.     

A solution approach based on Benders decomposition for the preventive maintenance scheduling problem of a stochastic large-scale energy system

This paper describes a Benders decomposition-based framework for solving the large scale energy management problem that was posed for the ROADEF 2010 challenge. The problem was taken from the power industry and entailed scheduling the outage dates for a set of nuclear power plants, which need to be regularly taken down for refueling and maintenance, in such a way that the expected cost of meeting the power demand in a number of potential scenarios is minimized. We show that the problem structure naturally lends itself to Benders decomposition; however, not all constraints can be included in the mixed integer programming model. We present a two phase approach that first uses Benders decomposition to solve the linear programming relaxation of a relaxed version of the problem. In the second phase, integer solutions are enumerated and a procedure is applied to make them satisfy constraints not included in the relaxed problem. To cope with the size of the formulations arising in our approach we describe efficient preprocessing techniques to reduce the problem size and show how aggregation can be applied to each of the subproblems. Computational results on the test instances show that the procedure competes well on small instances of the problem, but runs into difficulty on larger ones. Unlike heuristic approaches, however, this methodology can be used to provide lower bounds on solution quality.