Modeling formulation and a new heuristic for the railroad blocking problem

The railroad blocking problem is an important issue at the tactical level of railroad freight transportation. This problem consists of determining paths between the origins and destinations of each shipment to minimize the operating and user costs while satisfying the railroad supply and demand restrictions. A mixed-integer program (MIP) is developed to find the optimal paths, and a new heuristic is developed to solve the proposed model. This heuristic decomposes the model into two sub-problems of manageable size and then provides feasible solutions. We discuss the performance of the proposed heuristic for a set of instances with up to 90 stations. A comparison with the CPLEX MIP solver shows that the heuristic gives the exact solution for 10 out of 15 instances. For the remaining instances, the heuristic obtained solutions within a tolerance of 0.03–0.84%. Furthermore, compared with the CPLEX MIP solver, the heuristic reduced the run time by an average of 85% for all 15 instances. Finally, we present the computational results of the heuristic applied to Iranian railroads.     

Near-optimal MIP solutions for preference based self-scheduling

Making a high quality staff schedule is both difficult and time consuming for any company that has employees working on irregular schedules. We formulate a mixed integer program (MIP) to find a feasible schedule that satisfies all hard constraints while minimizing the soft constraint violations as well as satisfying as many of the employees’ requests as possible. We present the MIP model and show the result from four real world companies and institutions. We also compare the results with those of a local search based algorithm that is designed to emulate the solution strategies when the schedules are created manually. The results show that using near-optimal solutions from the MIP model, with a relative MIP gap of around 0.01–0.1, instead of finding the optimal solution, allows us to find very good solutions in a reasonable amount of time that compare favorably with both the manual solutions and the solutions found by the local search based algorithm.     

Optimizing specimen collection for processing in clinical testing laboratories

We study the logistics of specimen collection for a clinical testing laboratory that serves sites dispersed in an urban area. The specimens that accumulate at the customer sites throughout the working day are transported to the laboratory for processing. The problem is to construct and schedule a series of tours to collect the accumulated specimens from the sites throughout the day. Two hierarchical objectives are considered: (i) maximizing the amount of specimens processed by the next morning, and (ii) minimizing the daily transportation cost. We show that the problem is NP-hard and formulate a linear Mixed Integer Programming (MIP) model to solve the bicriteria problem in two levels. We characterize properties of optimal solutions and develop a heuristic approach based on solving the MIP model with additional constraints that seeks for feasible solutions with specific characteristics. To evaluate the performance of this approach, we provide an upper bounding scheme on the daily processed amount, and develop two relaxed MIP models to generate lower bounds on the daily transportation cost. The effectiveness of the proposed solution approach is evaluated using realistic problem instances. Insights on key problem parameters and their effects on the solutions are extracted by further experiments.     

Models and algorithms for a staff scheduling problem

We present mathematical models and solution algorithms for a family of staff scheduling problems arising in real life applications. In these problems, the daily assignments to be performed are given and the durations (in days) of the working and rest periods for each employee in the planning horizon are specified in advance, whereas the sequence in which these working and rest periods occur, as well as the daily assignment for each working period, have to be determined. The main objective is the minimization of the number of employees needed to perform all daily assignments in the horizon. We decompose the problem into two steps: the definition of the sequence of working and rest periods (called pattern) for each employee, and the definition of the daily assignment to be performed in each working period by each employee. The first step is formulated as a covering problem for which we present alternative ILP models and exact enumerative algorithms based on these models. Practical experience shows that the best approach is based on the model in which variables are associated with feasible patterns and generated either by dynamic programming or by solving another ILP. The second step is stated as a feasibility problem solved heuristically through a sequence of transportation problems. Although in general this procedure may not find a solution (even if one exists), we present sufficient conditions under which our approach is guaranteed to succeed. We also propose an iterative heuristic algorithm to handle the case in which no feasible solution is found in the second step. We present computational results on real life instances associated with an emergency call center. The proposed approach is able to determine the optimal solution of instances involving up to several hundred employees and a working period of up to 6 months. Mathematics Subject Classification (2000): 90B70, 90C10, 90C27, 90C39, 90C57, 90C59     

Proximity search for 0-1 mixed-integer convex programming

In this paper we investigate the effects of replacing the objective function of a 0-1 mixed-integer convex program (MIP) with a “proximity” one, with the aim of using a black-box solver as a refinement heuristic. Our starting observation is that enumerative MIP methods naturally tend to explore a neighborhood around the solution of a relaxation. A better heuristic performance can however be expected by searching a neighborhood of an integer solution—a result that we obtain by just modifying the objective function of the problem at hand. The relationship of this approach with primal integer methods is also addressed. Promising computational results on different proof-of-concept implementations are presented, suggesting that proximity search can be quite effective in quickly refining a given feasible solution. This is particularly true when a sequence of similar MIPs has to be solved as, e.g., in a column-generation setting.     

Algorithms for effective transfer of ballast for an oil installation

The problem considered is to transfer ballast (water) between ballast tanks in an offshore production platform in a fast and efficient way, and at the same time maintain certain criteria regarding the platform’s safety, stability and strength. In case of an emergency situation, the algorithm must return a solution in short time. Two alternative algorithms are evaluated; one mixed integer programming (MIP) model and one heuristic algorithm. It is shown that the much simpler heuristic algorithm yields satisfactory solutions in almost no time, while the MIP model takes up to several minutes to come to a solution. The heuristic algorithm is installed in control systems for a platform operating in the North Sea and the experience so far has been good.     

Base station location and channel allocation in a cellular network with emergency coverage requirements

The location of base stations (BS) and the allocation of channels are of paramount importance for the performance of cellular radio networks. Also cellular service providers are now being driven by the goal to enhance performance, particularly as it relates to the receipt and transmission of emergency crash notification messages generated by automobile telematics systems. In this paper, a Mixed Integer Programming (MIP) problem is proposed, which integrates into the same model the base station location problem, the frequency channel assignment problem and the emergency notification problem. The purpose of unifying these three problems in the same model is to treat the tradeoffs among them, providing a higher quality solution to the cellular system design. Some properties of the formulation are proposed that give us more insight into the problem structure. An instance generator is developed that randomly creates test problems. A few greedy heuristics are proposed to obtain quick solutions that turn out to be very good in some cases. To further improve the optimality gap, we develop a Lagrangean heuristic technique that builds on the solution obtained by the greedy heuristics. Finally, the performance of these methods is analyzed by extensive numerical tests and a sample case study is presented.     

Solving the CLSP by a Tabu Search Heuristic

The multi-item, single-level, capacitated, dynamic lot-sizing problem, commonly abbreviated as CLSP, is considered. The problem is cast in a tight mixed-integer programming model (MIP); tight in the sense that the gap between the optimal value of MIP and that of its linear programming relaxation (LP) is small. The LP relaxation of MIP is then solved by column generation. The resulting feasible solution is further improved by adopting the corresponding set-up schedule and re-optimizing variable costs by solving a minimum-cost network flow (trans-shipment) problem. Subsequently, the improved solution is used as a starting solution for a tabu search procedure, with the worth of moves assessed using the same trans-shipment problem. Results of computational testing of benchmark problem instances are presented. They show that the heuristic solutions obtained are effective, in that they are extremely close to the best known solutions. The computational efficiency makes it possible to solve realistically large problem instances routinely on a personal computer; in particular, the solution procedure is most effective, in terms of solution quality, for larger problem instances.     

DEA based dimensionality reduction for classification problems satisfying strict non-satiety assumption

This study shows how data envelopment analysis (DEA) can be used to reduce vertical dimensionality of certain data mining databases. The study illustrates basic concepts using a real-world graduate admissions decision task. It is well known that cost sensitive mixed integer programming (MIP) problems are NP-complete. This study shows that heuristic solutions for cost sensitive classification problems can be obtained by solving a simple goal programming problem by that reduces the vertical dimension of the original learning dataset. Using simulated datasets and a misclassification cost performance metric, the performance of proposed goal programming heuristic is compared with the extended DEA-discriminant analysis MIP approach. The holdout sample results of our experiments shows that the proposed heuristic approach outperforms the extended DEA-discriminant analysis MIP approach.     

A multi-class multi-level capacitated lot sizing model

When demand loading is higher than available capacity, it takes a great deal of effort for a traditional MRP system to obtain a capacity-feasible production plan. Also, the separation of lot sizing decisions and capacity requirement planning makes the setup decisions more difficult. In a practical application, a production planning system should prioritize demands when allocating manufacturing resources. This study proposes a planning model that integrates all MRP computation modules. The model not only includes multi-level capacitated lot sizing problems but also considers multiple demand classes. Each demand class corresponds to a mixed integer programming (MIP) problem. By sequentially solving the MIP problems according to their demand class priorities, this proposed approach allocates finite manufacturing resources and generates feasible production plans. In this paper we experiment with three heuristic search algorithms: (1) tabu search; (2) simulated annealing, and (3) genetic algorithm, to solve the MIP problems. Experimental designs and statistical methods are used to evaluate and analyse the performance of these three algorithms. The results show that tabu search and simulated annealing perform best in the confirmed order demand class and forecast demand class, respectively.     

Scheduling a hybrid assembly-differentiation flowshop to minimize total flow time

This study considers a hybrid assembly-differentiation flowshop scheduling problem (HADFSP), in which there are three production stages, including components manufacturing, assembly, and differentiation. All the components of a job are processed on different machines at the first stage. Subsequently, they are assembled together on a common single machine at the second stage. At the third stage, each job of a particular type is processed on a dedicated machine. The objective is to find a job schedule to minimize total flow time (TFT). At first, a mixed integer programming (MIP) model is formulated and then some properties of the optimal solution are presented. Since the NP-hardness of the problem, two fast heuristics (SPT-based heuristic and NEH-based heuristic) and three hybrid meta-heuristics (HGA-VNS, HDDE-VNS and HEDA-VNS) are developed for solving medium- and large-size problems. In order to evaluate the performances of the proposed algorithms, a lower bound for the HADFSP with TFT criteria (HADFSP-TFT) is established. The MIP model and the proposed algorithms are compared on randomly generated problems. Computational results show the effectiveness of the MIP model and the proposed algorithms. The computational analysis indicates that, in average, the HDDE-VNS performs better and more robustly than the other two meta-heuristics, whereas the NEH heuristic consume little time and could reach reasonable solutions.     

A graph-pair representation and MIP-model-based heuristic for the unequal-area facility layout problem

Owing to its theoretical as well as practical significance, the facility layout problem with unequal-area departments has been studied for several decades, with a wide range of heuristic and a few exact solution procedures developed by numerous researchers. In one of the exact procedures, the facility layout problem is formulated as a mixed-integer programming (MIP) model in which binary (0/1) variables are used to prevent departments from overlapping with one another. Obtaining an optimal solution to the MIP model is difficult, and currently only problems with a limited number of departments can be solved to optimality. Motivated by this situation, we developed a heuristic procedure which uses a “graph pair” to determine and manipulate the relative location of the departments in the layout. The graph-pair representation technique essentially eliminates the binary variables in the MIP model, which allows the heuristic to solve a large number of linear programming models to construct and improve the layout in a comparatively short period of time. The search procedure to improve the layout is driven by a simulated annealing algorithm. The effectiveness of the proposed graph-pair heuristic is demonstrated by comparing the results with those reported in recent papers. Possible extensions to the graph-pair representation technique are discussed at the end of the paper.     

A Comparative Study of Multiple-Objective Metaheuristics on the Bi-Objective Set Covering Problem and the Pareto Memetic Algorithm

Many organizations face employee scheduling problems under conditions of variable demand for service over the course of an operating day and across a planning horizon. These organizations are concerned with the tour scheduling problem that involves assigning shifts and break times to the work days of employees and allocating days off to individual work schedules. Nowadays, organizations try to adopt various scheduling flexibility alternatives to meet the fluctuating service demand. On the other hand, they have also realized that providing employee productivity and satisfaction is as much important as meeting the service demand. Up to date, tour scheduling solution approaches have neglected considering employee preferences and tried to develop work schedules for employees in a subsequent step. This paper presents a goal programming model that implicitly represents scheduling flexibility and also incorporates information about the preferred working patterns of employees. After solving the proposed model, a work schedule will be generated for each employee without requiring a further step for the assignment of shifts, break times, and work days to employees. The model is capable of handling multiple scheduling objectives, and it can produce optimal solutions in very short computing times.     

A column generation approach for an employee scheduling problem with multiple shifts and work locations

This paper is concerned with the problem of assigning employees to a number of work centres taking into account employees' expressed preferences for specific shifts, off-days, and work centres. This particular problem is faced by the Kuwait National Petroleum Corporation that hires a firm to prepare schedules for assigning employees to about 86 stations distributed all over Kuwait. The number of variables in a mixed-integer programming model formulated for this problem is overwhelming, and hence, a direct solution to even the continuous relaxation of this model for relatively large-scale instances is inconceivable. However, we demonstrate that a column generation method, which exploits the special structures of the model, can readily solve the continuous relaxation of the model. Based on this column generation construct, we develop an effective heuristic to solve the problem. Computational results indicate that the proposed approach can facilitate the generation of good-quality schedules for even large-scale problem instances in a reasonable time.     

A greedy heuristic for the capacitated minimum spanning tree problem

This paper develops a greedy heuristic for the capacitated minimum spanning tree problem (CMSTP), based on the two widely known methods of Prim and of Esau–Williams. The proposed algorithm intertwines two-stages: an enhanced combination of the Prim and Esau–Williams approaches via augmented and synthetic node selection criteria, and an increase of the feasible solution space by perturbing the input data using the law of cosines. Computational tests on benchmark problems show that the new heuristic provides extremely good performance results for the CMSTP, justifying its effectiveness and robustness. Furthermore, excluding the feasible space expansion, we show that we can still obtain good quality solutions in very short computational times.     

Bridging the gap between self schedules and feasible schedules in staff scheduling

Every company that has employees working on irregular schedules must deal with the difficult and time consuming problem of creating feasible schedules for the employees. We introduce an algorithm that takes a partial schedule created by requests from employees and creates feasible schedule where most of the employee’s requests are unchanged, while still making sure that rules and regulations are not violated. The algorithm is based on independent modules, which can be executed in any order, and each module tries to emulate some action taken by a staff manager. Our goal is to create a transparent and fair system that creates feasible schedules of high quality, but also a system where the employees can get an explanation and justification for every change that the algorithm makes to the employee requests. By emulating the actions of staff managers, the algorithm is easily understood by staff managers and, using detailed logs of any action, make any decision easy to explain to the employees. We will present the algorithm and show results from four real world companies and institutions. The results show that a simple module based heuristic can get good results and create fair and feasible schedules that encourage employees to participate in the self-scheduling process.     

Weekly staff scheduling with workstation group restrictions

This paper addresses the weekly adjustment problem for staff scheduling when movement restrictions exist between workstation groups (WSGs). In practice, it is common for employees to be organized into physical or logical groups to match the layout of a facility or to facilitate managerial oversight. A complication in the problem arises when each employee is required to spend more time at his or her assigned home base during the week than at any other WSG. This conflicts with a common strategy of reassigning employees to different WSGs when idle time exists in their schedules. Ordinarily, the full problem is tackled with a two-phase approach, where optimal shifts and overtime allocations are first derived and then tasks are assigned. When movement restrictions exist in a facility, this approach is no longer practical or even possible for all but the smallest instances. Alternatively, a new model is proposed that integrates WSG restrictions with the shift scheduling and task assignment constraints. The model takes the form of a large-scale integer program and is solved with one of two decomposition heuristics. The first splits the movement restrictions network into manageable pieces; the second uses column generation to identify good individual schedules that are used to construct a set-covering-type master problem. A solution to the master problem provides a feasible solution to the original integer program. Extensive testing was done with data obtained from the U.S. Postal Service mail processing and distribution center in Dallas. The results show that good feasible solutions can be obtained in less than an hour.     

Short-Term Capacity Adjustment with Offline Production for a Flexible Manufacturing System under Abnormal Disturbances

Large production variations caused by abnormal disturbances can significantly reduce the production capacity of a flexible manufacturing system (FMS). To prevent production delays, short-term capacity adjustment strategies can be used to augment the capacity of the FMS, such as working overtime, using alternative tools that are suited for faster processing, and producing parts outside of the FMS. We propose a mixed integer programming (MIP) model to obtain an optimal production plan for a multi-machine FMS. Our model evaluates both the FMS loading decision and the effective use of short-term capacity adjustment strategies to minimize the total part production cost. We develop an iterative procedure to solve the model that uses the Lagrangian relaxation method for finding lower bounds and a Lagrangian heuristic for obtaining feasible solutions. The procedure exploits certain special structures found in the Lagrangian multipliers which enable us to obtain good solutions to reasonably large test problems quickly.     

Exploring relaxation induced neighborhoods to improve MIP solutions

Given a feasible solution to a Mixed Integer Programming (MIP) model, a natural question is whether that solution can be improved using local search techniques. Local search has been applied very successfully in a variety of other combinatorial optimization domains. Unfortunately, local search relies extensively on the notion of a solution neighborhood, and this neighborhood is almost always tailored to the structure of the particular problem being solved. A MIP model typically conveys little information about the underlying problem structure. This paper considers two new approaches to exploring interesting, domain-independent neighborhoods in MIP. The more effective of the two, which we call Relaxation Induced Neighborhood Search (RINS), constructs a promising neighborhood using information contained in the continuous relaxation of the MIP model. Neighborhood exploration is then formulated as a MIP model itself and solved recursively. The second, which we call guided dives, is a simple modification of the MIP tree traversal order. Loosely speaking, it guides the search towards nodes that are close neighbors of the best known feasible solution. Extensive computational experiments on very difficult MIP models show that both approaches outperform default CPLEX MIP and a previously described approach for exploring MIP neighborhoods (local branching) with respect to several different metrics. The metrics we consider are quality of the best integer solution produced within a time limit, ability to improve a given integer solution (of both good and poor quality), and time required to diversify the search in order to find a new solution.Mathematics Subject Classification (2000):20E28, 20G40, 20C20Acknowledgement We wish to thank the two anonymous referees for their helpful comments.     

A dual ascent procedure for the set partitioning problem

The set partitioning problem is a fundamental model for many important real-life transportation problems, including airline crew and bus driver scheduling and vehicle routing.In this paper we propose a new dual ascent heuristic and an exact method for the set partitioning problem. The dual ascent heuristic finds an effective dual solution of the linear relaxation of the set partitioning problem and it is faster than traditional simplex based methods. Moreover, we show that the lower bound achieved dominates the one achieved by the classic Lagrangean relaxation of the set partitioning constraints. We describe a simple exact method that uses the dual solution to define a sequence of reduced set partitioning problems that are solved by a general purpose integer programming solver. Our computational results indicate that the new bounding procedure is fast and produces very good dual solutions. Moreover, the exact method proposed is easy to implement and it is competitive with the best branch and cut algorithms published in the literature so far.