Discrete and continuous time representations and mathematical models for large production scheduling problems: A case study from the pharmaceutical industry

The underlying time framework used is one of the major differences in the basic structure of mathematical programming formulations used for production scheduling problems. The models are either based on continuous or discrete time representations. In the literature there is no general agreement on which is better or more suitable for different types of production or business environments. In this paper we study a large real-world scheduling problem from a pharmaceutical company. The problem is at least NP-hard and cannot be solved with standard solution methods. We therefore decompose the problem into two parts and compare discrete and continuous time representations for solving the individual parts. Our results show pros and cons of each model. The continuous formulation can be used to solve larger test cases and it is also more accurate for the problem under consideration.     

A Lagrangian decomposition approach for the pump scheduling problem in water networks

Dynamic pricing has become a common form of electricity tariff, where the price of electricity varies in real time based on the realized electricity supply and demand. Hence, optimizing industrial operations to benefit from periods with low electricity prices is vital to maximizing the benefits of dynamic pricing. In the case of water networks, energy consumed by pumping is a substantial cost for water utilities, and optimizing pump schedules to accommodate for the changing price of energy while ensuring a continuous supply of water is essential. In this paper, a Mixed-Integer Non-linear Programming (MINLP) formulation of the optimal pump scheduling problem is presented. Due to the non-linearities, the typical size of water networks, and the discretization of the planning horizon, the problem is not solvable within reasonable time using standard optimization software. We present a Lagrangian decomposition approach that exploits the structure of the problem leading to smaller problems that are solved independently. The Lagrangian decomposition is coupled with a simulation-based, improved limited discrepancy search algorithm that is capable of finding high quality feasible solutions. The proposed approach finds solutions with guaranteed upper and lower bounds. These solutions are compared to those found by a mixed-integer linear programming approach, which uses a piecewise-linearization of the non-linear constraints to find a global optimal solution of the relaxation. Numerical testing is conducted on two real water networks and the results illustrate the significant costs savings due to optimizing pump schedules.     

Evaluation of mathematical models for flexible job-shop scheduling problems

With the rapid development in computer technologies, mathematical programming-based technique to solve scheduling problems is significantly receiving attention from researchers. Although, it is not efficient solution method due to the NP-hard structure of these problems, mathematical programming formulation is the first step to develop an effective heuristic. Numerous comparative studies for variety scheduling problems have appeared over the years. But in our search in literature there is not an entirely review for mathematical formulations of flexible job shop scheduling problems (FJSP). In this paper, four the most widely used formulations of the FJSP are compiled from literature and a time-indexed model for FJSP is proposed. These formulations are evaluated under three categories that are distinguished by the type of binary variable that they rely on for using of sequencing operations on machines. All five formulations compared and results are presented.     

Solution approaches for the soft drink integrated production lot sizing and scheduling problem

In this paper we present a mixed integer programming model that integrates production lot sizing and scheduling decisions of beverage plants with sequence-dependent setup costs and times. The model considers that the industrial process produces soft drink bottles in different flavours and sizes, and it is carried out in two production stages: liquid preparation (stage I) and bottling (stage II). The model also takes into account that the production bottleneck may alternate between stages I and II, and a synchronisation of the production between these stages is required. A relaxation approach and several strategies of the relax-and-fix heuristic are proposed to solve the model. Computational tests with instances generated based on real data from a Brazilian soft drink plant are also presented. The results show that the solution approaches are capable of producing better solutions than those used by the company.     

Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs

We study a two-machine flowshop scheduling problem with time-dependent deteriorating jobs, i.e. the processing times of jobs are an increasing function of their starting time. The objective is to minimize the total completion time subject to minimum makespan. We propose a mixed integer programming model, and develop two pairwise interchange algorithms and a branch-and-bound procedure to solve the problem while using several dominance conditions to limit the size of the search tree. Several polynomial-time solvable special cases are discussed. Finally, numerical studies are performed to examine the effectiveness and the efficiency of the proposed algorithms.     

Divide-and-price: A decomposition algorithm for solving large railway crew scheduling problems

The railway crew scheduling problem consists of generating crew duties to operate trains at minimal cost, while meeting all work regulations and operational requirements. Typically, a railway operation uses tens of thousands of train movements (trips) and requires thousands of crew members to be assigned to these trips. Despite the large size of the problem, crew schedules need to be generated in short time, because large parts of the train schedule are not finalized until few days before operation.     

A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports

In this research, two crucial optimization problems of berth allocation and yard assignment in the context of bulk ports are studied. We discuss how these problems are interrelated and can be combined and solved as a single large scale optimization problem. More importantly we highlight the differences in operations between bulk ports and container terminals which highlights the need to devise specific solutions for bulk ports. The objective is to minimize the total service time of vessels berthing at the port. We propose an exact solution algorithm based on a branch and price framework to solve the integrated problem. In the proposed model, the master problem is formulated as a set-partitioning problem, and subproblems to identify columns with negative reduced costs are solved using mixed integer programming. To obtain sub-optimal solutions quickly, a metaheuristic approach based on critical-shaking neighborhood search is presented. The proposed algorithms are tested and validated through numerical experiments based on instances inspired from real bulk port data. The results indicate that the algorithms can be successfully used to solve instances containing up to 40 vessels within reasonable computational time.     

A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times

We consider a scheduling problem in which the processing time of each job deteriorates, i.e. it increases as time passes after the release date of the job. We present a dynamic programming algorithm coupled with upper bounding and lower bounding techniques to compute exact solutions. We report on problem instances of different size and we analyze the dependence between the ranges to which the data belong and the computing time.     

A heuristic multi-start decomposition approach for optimal design of serial machining lines

We study an optimal design problem for serial machining lines. Such lines consist of a sequence of stations. At every station, the operations to manufacture a product are grouped into blocks. The operations within each block are performed simultaneously by the same spindle head and the blocks of the same station are executed sequentially. The inclusion and exclusion constraints for combining operations into blocks and stations as well as the precedence constraints on the set of operations are given. The problem is to group the operations into blocks and stations minimizing the total line cost. A feasible solution must respect the given cycle time and all given constraints. In this paper, a heuristic multi-start decomposition approach is proposed. It utilizes a decomposition of the initial problem into several sub-problems on the basis of a heuristic solution. Then each obtained sub-problem is solved by an exact algorithm. This procedure is repeated many times, each time it starts with a new heuristic solution. Computational tests show that the proposed approach outperforms simple heuristic algorithms for large-scale problems.     

A hybrid Outer-Approximation/Benders Decomposition algorithm for the single allocation hub location problem under congestion

An efficient procedure that concurrently generates Outer-Approximation and Benders cuts is devised to tackle the single allocation hub location problem under congestion, an MINLP. The proposed method is able to optimally solve large instances (up to 200 nodes) in reasonable time. The combination of both cuts is an algorithmic novelty.     

Lagrangian heuristics for scheduling new product development projects in the pharmaceutical industry

To stay ahead of their competition, pharmaceutical firms must make effective use of their new product development (NPD) capabilities by efficiently allocating its analytical, clinical testing and manufacturing resources across various drug development projects. The resulting project scheduling problems involve coordinating hundreds of testing and manufacturing activities over a period of several quarters. Most conventional integer programming approaches are computationally impractical for problems of this size, while priority rule-driven heuristics seldom provide consistent solution quality. We propose a Lagrangian decomposition (LD) heuristic that exploits the special structure of these problems. Some resources (typically manpower) are shared across all on-going projects while others (typically equipment) are specific to individual project categories. Our objective function is a weighted discounted cost expressed in terms of activity completion times. The LD heuristics were subjected to a comprehensive experimental study based on typical operational instances. While the conventional “Reward–Risk” priority rule heuristic generates duality gaps between 47–58%, the best LD heuristic achieves duality gaps between 10–20%. The LD heuristics also yield makespan reductions of over 30% over the Reward–Risk priority rule.     

A heuristic for the long-term electricity generation planning problem using the Bloom and Gallant formulation

Long-term power planning is a stochastic problem often confronted by electrical utilities in liberalized markets. One can model it for profit maximization—using market-price estimation functions for each interval—by posing it as a quadratic programming problem with some linear equalities and an exponential number of load-matching linear inequality constraints.     

The efficient solution of large-scale linear programming problems—some algorithmic techniques and computational results

First, this paper presents the results of experiments with algorithmic techniques for efficiently solving medium and large scale linear and mixed integer programming problems. The techniques presented here are either original or recent.The solution of a great number of problems has shown that efficient problem solving requires automatic adaptation of algorithmic techniques upon problem characteristics. We show when a given technique should be used for a particular problem.The last part of this paper describes an attempt to provide a powerful mathematical programming language, allowing an easy programming of specific studies on medium-size models such as the recursive use of LP or the build-up of algorithms based on the simplex method.All these features have been implemented in the IBM Mathematical Programming System, MPSX/370, and its feature MIP/370. Extensive numerical results and comparisons on real-life problems are provided and commented upon.Presented at the IXth International Symposium on Mathematical Programming in Budapest (1976).     

Optimization models for the single delay management problem in public transportation

Passengers travelling in public transportation networks often have to use different lines to cover the trip from their origin to the desired destination. As a consequence, the reliability of connections between vehicles is a key issue for the attractiveness of the intermodal transportation network and it is strongly affected by some unpredictable events like breakdowns or vehicle delays. In such cases, a decision is required to determine if the connected vehicles should wait for the delayed ones or keep their schedule. The delay management problem (DMP) consists in defining the wait/depart policy which minimizes the total delay on the network. In this work, we present two equivalent mixed integer linear programming models for the DMP with a single initial delay, able to reduce the number of variables with respect to the formulations proposed by the literature. The two models are solved by a branch and cut procedure and by a constraint generation approach respectively, and preliminary computational results are presented.     

Exact and heuristic methodologies for scheduling in hospitals: problems, formulations and algorithms

This text summarizes the PhD thesis defended by the author in January 2006 under the supervision of Professor Erik Demeulemeester at the Katholieke Universiteit Leuven. The thesis is written in English and is available from the author’s website (http://www.econ.kuleuven.be/jeroen.belien). In this research we propose a number of exact and heuristic algorithms for various scheduling problems encountered in hospitals. The emphasis lies on the design of new methodologies as well as on the applicability of the algorithms in real-life environments. The main contributions include a new decomposition approach for a particular class of staff scheduling problems, an extensive study of master surgery scheduling algorithms that aim at leveling the resultant bed occupancy and an innovative method for integrating nurse and surgery scheduling.      

A new exact discrete linear reformulation of the quadratic assignment problem

The quadratic assignment problem (QAP) is a challenging combinatorial problem. The problem is NP-hard and in addition, it is considered practically intractable to solve large QAP instances, to proven optimality, within reasonable time limits. In this paper we present an attractive mixed integer linear programming (MILP) formulation of the QAP. We first introduce a useful non-linear formulation of the problem and then a method of how to reformulate it to a new exact, compact discrete linear model. This reformulation is efficient for QAP instances with few unique elements in the flow or distance matrices. Finally, we present optimal results, obtained with the discrete linear reformulation, for some previously unsolved instances (with the size n = 32 and 64), from the quadratic assignment problem library, QAPLIB.     

A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process

One of the largest bottlenecks in iron and steel production is the steelmaking-continuous casting (SCC) process, which consists of steel-making, refining and continuous casting. The SCC scheduling is a complex hybrid flowshop (HFS) scheduling problem with the following features: job grouping and precedence constraints, no idle time within the same group of jobs and setup time constraints on the casters. This paper first models the scheduling problem as a mixed-integer programming (MIP) problem with the objective of minimizing the total weighted earliness/tardiness penalties and job waiting. Next, a Lagrangian relaxation (LR) approach relaxing the machine capacity constraints is presented to solve the MIP problem, which decomposes the relaxed problem into two tractable subproblems by separating the continuous variables from the integer ones. Additionally, two methods, i.e., the boundedness detection method and time horizon method, are explored to handle the unboundedness of the decomposed subproblems in iterations. Furthermore, an improved subgradient level algorithm with global convergence is developed to solve the Lagrangian dual (LD) problem. The computational results and comparisons demonstrate that the proposed LR approach outperforms the conventional LR approaches in terms of solution quality, with a significantly shorter running time being observed.     

Design of progressively censored group sampling plans for Weibull distributions: An optimization problem

Optimization algorithms provides efficient solutions to many statistical problems. Essentially, the design of sampling plans for lot acceptance purposes is an optimization problem with several constraints, usually related to the quality levels required by the producer and the consumer. An optimal acceptance sampling plan is developed in this paper for the Weibull distribution with unknown scale parameter. The proposed plan combines grouping of items, sudden death testing in each group and progressive group removals, and its decision criterion is based on the uniformly most powerful life test. A mixed integer programming problem is first solved for determining the minimum number of failures required and the corresponding acceptance constant. The optimal number of groups is then obtained by minimizing a balanced estimation of the expected test cost. Excellent approximately optimal solutions are also provided in closed-forms. The sampling plan is considerably flexible and allows to save experimental time and cost. In general, our methodology achieves solutions that are quite robust to small variations in the Weibull shape parameter. A numerical example about a manufacturing process of gyroscopes is included for illustration.     

A tabu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal

The scheduling problem in a container terminal is characterized by the coordination of different types of equipment. In this paper, we present an integrated model to schedule the equipment. The objective is to minimize the makespan, or the time it takes to serve a given set of ships. The problem is formulated as a Hybrid Flow Shop Scheduling problem with precedence and Blocking constraints (HFSS-B). A tabu search algorithm is proposed to solve this problem. Certain mechanisms are developed and introduced into the algorithm to assure its quality and efficiency. The performance of the tabu search algorithm is analyzed from the computational point of view.     

Genetic algorithms for supply-chain scheduling: A case study in the distribution of ready-mixed concrete

The coordination of just-in-time production and transportation in a network of partially independent facilities to guarantee timely delivery to distributed customers is one of the most challenging aspect of supply chain management. From a theoretical perspective, the timely production/distribution can be viewed as a hybrid combination of planning, scheduling and routing problems, each notoriously affected by nearly prohibitive combinatorial complexity. From a practical viewpoint, the problem calls for a trade-off between risks and profits. This paper focuses on the ready-mixed concrete delivery: in addition to the mentioned complexity, strict time-constraints forbid both earliness and lateness of the supply. After developing a detailed model of the considered problem, we propose a novel meta-heuristic approach based on a hybrid genetic algorithm combined with constructive heuristics. A detailed case study derived from industrial data is used to illustrate the potential of the proposed approach.