Deterministic solution approach for some classes of nonlinear multilevel programs with multiple followers

In this paper we investigate multilevel programming problems with multiple followers in each hierarchical decision level. It is known that such type of problems are highly non-convex and hard to solve. A solution algorithm have been proposed by reformulating the given multilevel program with multiple followers at each level that share common resources into its equivalent multilevel program having single follower at each decision level. Even though, the reformulated multilevel optimization problem may contain non-convex terms at the objective functions at each level of the decision hierarchy, we applied multi-parametric branch-and-bound algorithm to solve the resulting problem that has polyhedral constraints. The solution procedure is implemented and tested for a variety of illustrative examples.     

Rotation cycle schedulings for multi-item production systems

Consider the production planning and scheduling on a single machine with finite constant production rate over a planning horizon N. For single-item production problem, we have characterised the structure of the optimal solution when N approaches to infinity. This result suggests a near optimal solution when the planning horizon N is large. For multi-item production problem, we restrict our analysis on the Rotation Cycle policies. Under the assumptions of the policy, we convert the problem into a generalised travelling salesman problem and hence a branch and bound algorithm is proposed to solve the problem. For a given error bound of the solution, the algorithm can be further simplified to determine a near-optimal rotation cycle.     

Development of a new approach for deterministic supply chain network design

This paper proposes a mixed integer linear programming model and solution algorithm for solving supply chain network design problems in deterministic, multi-commodity, single-period contexts. The strategic level of supply chain planning and tactical level planning of supply chain are aggregated to propose an integrated model. The model integrates location and capacity choices for suppliers, plants and warehouses selection, product range assignment and production flows. The open-or-close decisions for the facilities are binary decision variables and the production and transportation flow decisions are continuous decision variables. Consequently, this problem is a binary mixed integer linear programming problem. In this paper, a modified version of Benders’ decomposition is proposed to solve the model. The most difficulty associated with the Benders’ decomposition is the solution of master problem, as in many real-life problems the model will be NP-hard and very time consuming. In the proposed procedure, the master problem will be developed using the surrogate constraints. We show that the main constraints of the master problem can be replaced by the strongest surrogate constraint. The generated problem with the strongest surrogate constraint is a valid relaxation of the main problem. Furthermore, a near-optimal initial solution is generated for a reduction in the number of iterations.     

A scenario decomposition approach for stochastic production planning in sawmills

This study considers a real world stochastic multi-period, multi-product production planning problem. Motivated by the challenges encountered in sawmill production planning, the proposed model takes into account two important aspects: (i) randomness in yield and in demand; and (ii) set-up constraints. Rather than considering a single source of randomness, or ignoring set-up constraints as is typically the case in the literature, we retain all these characteristics while addressing real life-size instances of the problem. Uncertainties are modelled by a scenario tree in a multi-stage environment. In the case study, the resulting large-scale multi-stage stochastic mixed-integer model cannot be solved by using the mixed-integer solver of a commercial optimization package, such as CPLEX. Moreover, as the production planning model under discussion is a mixed-integer programming model lacking any special structure, the development of decomposition and cutting plane algorithms to obtain good solutions in a reasonable time-frame is not straightforward. We develop a scenario decomposition approach based on the progressive hedging algorithm, which iteratively solves the scenarios separately. CPLEX is then used for solving the sub-problems generated for each scenario. The proposed approach attempts to gradually steer the solutions of the sub-problems towards an implementable solution by adding some penalty terms in the objective function used when solving each scenario. Computational experiments for a real-world large-scale sawmill production planning model show the effectiveness of the proposed solution approach in finding good approximate solutions.     

Approximations for the Two-Machine Cross-Docking Flow Shop Problem

We consider in this article the Two-Machine Cross-Docking Flow Shop Problem, which is a special case of scheduling with typed tasks, where we have two types of tasks and one machine per type. Precedence constraints exist between tasks, but only from a task of the first type to a task of the second type. The precedence relation is thus a directed bipartite graph. Minimizing the makespan is strongly NP-hard even with unit processing times, but any greedy method yields a 2-approximation solution. In this paper, we are interested in establishing new approximability results for this problem. More specifically, we investigate three directions: list scheduling algorithms based on the relaxation of the resources, the decomposition of the problem according to the connected components of the precedence graph, and finally the search of the induced balanced subgraph with a bounded degree.     

Short-term financial planning with uncertain receipts and disbursements

The problem of short-term financial planning is to determine an optimal credit mix to meet the short-term cash needs and an optimal investment plan for excess cash. A number of linear optimization models have been developed to solve this problem, some of which are in practical use. The purpose of this paper is to generalize the assumptions of these models concerning the available information about future receipts and disbursements. It is presupposed that the financial officer has some idea as to the amount involved which, however, cannot be specified by a probability distribution. On the contrary, we assume that these ideas only permit qualitative probability statements such as the following:“That the difference between disbursements and receipts in a certain period lies in an interval I₁ is no less probable than that it lies in an interval I₂”.For this level of information we formulate a model for short-term financial planning, and we develop a solution procedure to determine the optimum financial alternatives. Finally, the entire procedure is demonstrated by a medium sized example.     

Medium-term hydro-thermal coordination via hydro and thermal subsystem decomposition

Summary This paper addresses the medium-term hydro-thermal coordination problem in an electric energy system. That is, the problem of finding the energy production of every power plant (hydro or thermal) in every subperiod of a given planning period, so that the customer load is supplied at minimum cost. The planning horizon is typically one to two months and the first week of this planning period is modeled in detail. The solution method proposed decomposes the problem in two subproblems corresponding to the hydro and thermal subsystems. These two subproblems are coordinated using a coordinating function for every subperiod. The coordinating function of a given subperiod expresses total production cost in that subperiod as a function of the total hydro production in that subperiod. The decomposition proposed makes it possible to use specialized algorithms to solve the hydro and thermal subproblems. This results in a very efficient computational procedure. From an experimental point of view the coordinating mechanism is robust. A case study is provided. It considers 61 thermal plants, a hydro system including 8 cascaded hydro plants and a 48 subperiods planning period.     

Two-dimensional Cutting Stock with Multiple Stock Sizes

In this paper an algorithm for a cutting stock problem in the wood industry is presented. Cuts are of guillotine type and requirements have to be met exactly, i.e. no over- or under-production is allowed. There are several different board sizes from which panels can be cut and the problem is to find the best mix of boards and respective cutting patterns that satisfies the demand for panels with minimum wastage. The heuristic algorithm uses a pattern-building procedure combined with an enumeration scheme for the mix of boards.     

Developing work schedules for an inter-city transit system with multiple driver types and fleet types

In developing work schedules, the job assignment flexibility exploits the variety of available skills, thus enabling the assignment of workers to perform different jobs. In this study, we investigate the problem of finding the mix of primary and secondary jobs in short term work schedules to meet, at minimum cost, the daily service requirements of an inter-city bus transit firm in Andra Pradesh India operating multiple fleet types. We formulate the problem as a set covering model with resource allocation constraints. We develop a branch-and-price procedure to solve the model. Computational results are provided.     

Capacitated dynamic lot-sizing problem with delivery/production time windows

In this paper we generalize the classical dynamic lot-sizing problem by considering production capacity constraints as well as delivery and/or production time windows. Utilizing an untraditional decomposition principle, we develop a polynomial-time algorithm for computing an optimal solution for the problem under the assumption of non-speculative costs. The proposed solution methodology is based on a dynamic programming algorithm that runs in O(nT⁴) time, where n is the number of demands and T is the length of the planning horizon.     

Heuristic solutions to the problem of routing school buses with multiple objectives

In this paper we address the problem of routing school buses in a rural area. We approach this problem with a node routing model with multiple objectives that arise from conflicting viewpoints. From the point of view of cost, it is desirable to minimise the number of buses used to transport students from their homes to school and back. From the point of view of service, it is desirable to minimise the time that a given student spends en route. The current literature deals primarily with single-objective problems and the models with multiple objectives typically employ a weighted function to combine the objectives into a single one. We develop a solution procedure that considers each objective separately and search for a set of efficient solutions instead of a single optimum. Our solution procedure is based on constructing, improving and then combining solutions within the framework of the evolutionary approach known as scatter search. Experimental testing with real data is used to assess the merit of our proposed procedure.     

Designing a two-echelon distribution network under demand uncertainty

This paper proposes a comprehensive methodology for the stochastic multi-period two-echelon distribution network design problem (2E-DDP) where product flows to ship-to-points are directed from an upper layer of primary warehouses to distribution platforms (DPs) before being transported to the ship-to-points. A temporal hierarchy characterizes the design level dealing with DP location and capacity decisions, as well as the operational level involving transportation decisions as origin-destination flows. These design decisions must be calibrated to minimize the expected distribution cost associated with the two-echelon transportation schema on this network under stochastic demand. We consider a multi-period planning horizon where demand varies dynamically from one planning period to the next. Thus, the design of the two-echelon distribution network under uncertain customer demand gives rise to a complex multi-stage decisional problem. Given the strategic structure of the problem, we introduce alternative modeling approaches based on two-stage stochastic programming with recourse. We solve the resulting models using a Benders decomposition approach. The size of the scenario set is tuned using the sample average approximation (SAA) approach. Then, a scenario-based evaluation procedure is introduced to post-evaluate the design solutions obtained. We conduct extensive computational experiments based on several types of instances to validate the proposed models and assess the efficiency of the solution approaches. The evaluation of the quality of the stochastic solution underlines the impact of uncertainty in the two-echelon distribution network design problem (2E-DDP).     

Optimization of chance constraint programming with sum-of-fractional objectives – An application to assembled printed circuit board problem

This paper presents a procedure to solve a chance constraint programming problem with sum-of-fractional objectives. The problem and the solution procedure are described with the help of a practical problem – assembled printed circuit boards (PCBs). Errors occurring during assembling PCBs are in general classified into three kinds, viz. machine errors, manual errors and other errors. These errors may lead to the rejection of the major portion of the production and hence result the manufacturer a huge loss. The problem is decomposed to have two objective functions; one is a sum-of-fractional objectives and the other is a non-linear objective with bounded constraints. The interest is to maximize the sum-of-fractional objectives and to minimize the non-linear objective, subject to stochastic and non-stochastic bounded environment. The first problem deals with the maximization of the profit (maximizing sum-of-fractional objectives) and the second deals with the minimization of the loss (errors), so as to obtain the maximum profit after removing the number of defective PCBs.     

A joint production and transportation planning problem with heterogeneous vehicles

We consider a manufacturer's planning problem to schedule order production and transportation to respective destinations. The manufacturer in this setting can use two vehicle types for outbound shipments. The first type is available in unlimited numbers. The availability of the second type, which is less expensive, changes over time. Motivated by some industry practices, we present formulations for three different solution approaches: the myopic solution, the hierarchical solution and the coordinated solution. These approaches vary in how the underlying production and transportation subproblems are solved, that is, sequentially versus jointly or heuristically versus optimally. We provide intractability proofs or polynomial-time exact solution procedures for the sub-problems and their special cases. We also compare the three solution approaches over a numerical study to quantify the savings from integration and explicit consideration of transportation availabilities. Our analytical and numerical results set a foundation and a need for a heuristic to solve the integrated problem. We thus propose a tabu search heuristic, which quickly generates near-optimal solutions.     

A Closed Queueing Maintenance Network with Two Repair Centres

In this paper we introduce a model to determine the maintenance float needed to maximize the availability of an operating system with N number of circulating units. An implicit enumeration algorithm is used as a solution technique to the closed queueing maintenance network with two types of repairs: minor and major repairs. It is shown that when there is no differentiation of repair type, this special case is obtained as a by-product of the two-repair-centre model. This paper assumes exponential failure times and exponential repair times with load-independent servers. The approach followed in this paper provides an approximate and simple way to solve the maintenance-float problem of this complex closed-network system.     

Scheduling orders for multiple product types to minimize total weighted completion time

We consider the problem of scheduling orders for multiple different product types in an environment with m dedicated machines in parallel. The objective is to minimize the total weighted completion time. Each product type is produced by one and only one of the m dedicated machines; that is, each machine is dedicated to a specific product type. Each order has a weight and may also have a release date. Each order asks for certain amounts of various different product types. The different products for an order can be produced concurrently. Preemptions are not allowed. Even when all orders are available at time 0, the problem has been shown to be strongly NP-hard for any fixed number (?2) of machines. This paper focuses on the design and analysis of efficient heuristics for the case without release dates. Occasionally, however, we extend our results to the case with release dates. The heuristics considered include some that have already been proposed in the literature as well as several new ones. They include various static and dynamic priority rules as well as two more sophisticated LP-based algorithms. We analyze the performance bounds of the priority rules and of the algorithms and present also an in-depth comparative analysis of the various rules and algorithms. The conclusions from this empirical analysis provide insights into the trade-offs with regard to solution quality, speed, and memory space.     

Integrating two-dimensional cutting stock and lot-sizing problems

The two-dimensional cutting stock problem (2DCSP) consists in the minimization of the number of plates used to cut a set of items. In industry, typically, an instance of this problem is considered at the beginning of each planning time period, what may result in solutions of poor quality, that is, excessive waste, when a set of planning periods is considered. To deal with this issue, we consider an integrated problem, in which the 2DCSP is extended from the solution in only a single production planning period to a solution in a set of production planning periods. The main difference of the approach in this work and the ones in the literature is to allow sufficiently large residual plates (leftovers) to be stored and cut in a subsequent period of the planning horizon, which may further help in the minimization of the waste. We propose two integrated integer programming models to optimize the combined two-dimensional cutting stock and lot-sizing problems, minimizing the total cost, which includes material, waste and storage costs. Two heuristics based on the industrial practice to solve the problem were also presented. Computational results for the proposed models and for the heuristics are presented and discussed.     

A cooperative inventory policy with deteriorating items for a two-echelon model

A cooperative inventory policy between supplier and buyer is proposed. Unlike other studies, we consider the case of deteriorating items and permit the completed back-order in the problem. We solve the problem without the condition of equal replenishments periods during a specified planning horizon and present a procedure to find the optimal solution. A case is presented to demonstrate the application of the proposed approach. The sensitivity analysis for a cooperation policy between supplier and buyer also are explored.     

Simultaneous production and maintenance planning for a single capacitated resource facing both a dynamic demand and intensive wear and tear

This paper presents a generic modeling framework to simultaneously decide about production quantities and maintenance operations for a capacitated resource facing a dynamic demand for different types of products. As the resource needs to be setup for each specific type of product, a lot-sizing problem occurs. In addition it is assumed that production causes intensive wear and tear. For this reason frequent maintenance activities need to be coordinated with the production operations in order to efficiently use the capacitated resource. A single generic model is presented to capture alternative forms of maintenance and different modes of interaction between maintenance and setups. As the model is numerically intractable for standard branch and bound algorithms, we solve it heuristically via a decomposition using a Fix-and-Optimize approach. Numerical results show that the proposed solution method produces high-quality results quickly. We further study the impact of simultaneous vs. sequential decisions about production and maintenance in the case of intensive wear and tear.     

Cost optimal periodic train scheduling

For real world railroad networks, we consider minimizing operational cost of train schedules which depend on choosing different train types of diverse speed and cost. We develop a mixed integer linear programming model for this train scheduling problem. For practical problem sizes, it seems to be impossible to directly solve the model within a reasonable amount of time. However, suitable decomposition leads to much better performance. In the first part of the decomposition, only the train type related constraints stay active. In the second part, using an optimal solution of this relaxation, we select and fix train types and try to generate a train schedule satisfying the remaining constraints. This decomposition idea provides the cornerstone for an algorithm integrating cutting planes and branch-and-bound. We present computational results for railroad networks from Germany and the Netherlands.