Capacitated multicommodity network flow problems with piecewise linear concave costs

Lagrangian techniques have been commonly used to solve the capacitated multi-commodity network flow problem with piecewise linear concave costs. In this paper, we show that the resulting lower bounds are no better than those obtained by the linear programming relaxation and focus on developing algorithms based on the latter. For that purpose, we characterize structural properties of the optimal solution of the linear programming relaxation and propose a heuristic solution approach that uses these properties to transform the fractional solution into an integer one. Our computational experiments show the effectiveness of the algorithm.     

A novel integer programming formulation with logic cuts for the U-shaped assembly line balancing problem

U-shaped assembly lines are regarded as an efficient configuration in Just-In-Time manufacturing. Balancing the workload in these lines is an unsolved problem that attracted significant research within the past two decades. We present a novel integer programming formulation for U-shaped line balancing problems, where cycle time, the interval between two consecutive outputs, is known and the aim is to minimize the number of workstations. To enhance the efficiency of the LP relaxation of the new formulation, we present three types of logic cuts (assignable-station-cuts, task-assignment-cuts and knapsack-cuts) that exploit the inherent logic of the problem structure. The new formulation and logic cuts are tested on an extensive set of benchmark problems to provide a comparative analysis with the existing models in the literature. The results show that our novel formulation augmented by assignable-station-cuts is significantly better than the previous formulations.     

A comparison of mixed integer programming formulations of the capacitated lot-sizing problem

We propose a novel mixed integer programming formulation for the capacitated lot-sizing problem with set-up times and set-up carryover. We compare our formulation to two earlier formulations, the Classical and Modified formulations, and a more recent formulation due to Suerie and Stadtler. Extensive computational experiments show that our formulation consistently outperforms the Classical and Modified formulations in terms of CPU time and solution quality. It is competitive with the Suerie–Stadtler (S&S) formulation, but outperforms all other formulations on the most challenging instances, those with low-capacity slack and a dense jobs matrix. We show that some of the differences in the performance of these various formulations arise from their different use of binary variables to represent production or set-up states. We also show that the LP relaxation of our Novel formulation provides a tighter lower bound than that of the Modified formulation. Our experiments demonstrate that, while the S&S formulation provides a much tighter LP bound, the Novel formulation is better able to exploit the intelligence of the CPLEX solution engine.     

A Lagrangean heuristic for integrated production and transportation planning problems in a dynamic, multi-item, two-layer supply chain

We present a Lagrangean-based decomposition that is used to generate solutions for an integrated production and transportation planning problem in a two-stage supply chain. This supply chain consists of a number of facilities, each capable of producing the final products, and a number of retailers. It is assumed that the retailers' demands are known and deterministic, and that there are production capacity constraints. The problem is formulated as a multi-commodity network flow problem with fixed charge costs which is a NP-hard problem. An alternative formulation is provided whose linear programming relaxation gives tighter lower bounds. The quality of the lower and upper bounds from the Lagrangean decomposition is tested on a large set of randomly generated problems.     

A multi-commodity supply chain design problem

We consider a multi-commodity supply chain design problem in which we need to determine where to locate facilities and how to allocate customers to facilities so as to minimize total costs. The cost associated with each facility exhibits economies of scale. We show that this problem can be formulated as a nonlinear integer program and propose a Lagrangian-relaxation solution algorithm. By exploiting the structure of the problem, we find a low-order polynomial algorithm for the nonlinear integer program that must be solved in solving the Lagrangian relaxation subproblems. We also compare our approach with an existing algorithm.     

Linear programming and Lagrangian relaxation heuristics for designing a material flow network on a block layout

This paper focuses on the problem of designing a material flow network for a given block layout. For an efficient design of a network, we simultaneously consider locations of input and output points, flow paths, and the smoothness of material flow paths. A mixed integer programming formulation is given for the problem with the objective of minimising the sum of transportation cost, cost related to flow paths, and penalty cost for non-smooth flows, i.e., flows with many turns. We suggest two heuristic algorithms based on the linear programming relaxation and the Lagrangian relaxation techniques. To evaluate performance of the suggested algorithms, a series of computational experiments is performed on well-known problem instances as well as randomly generated test problems. Results show that the suggested algorithms give good solutions in a reasonable amount of computation time.     

Optimal flow path design of unidirectional AGV systems

This paper describes an alternative formulation of the AGV flow path layout (FPL) problem which was first formulated by Gaskins and Tanchoco (1987) as a zero-one integer programming problem. A computationally efficient procedure is proposed which is based on the branch-and-bound technique. An algorithm for satisfying the reachability condition for nodes in the AGV flow path network is also presented. A simple illustrative example is discussed to demonstrate the procedure, and a more complex problem is also given.     

Matheuristic approaches for Q-coverage problem versions in wireless sensor networks

This article deals with sensor coverage scheduling in wireless sensor networks subject to Q-coverage constraints. The main concern is to maximize the network lifetime, while ensuring that each target is covered by a given number of sensors. Three different variations of this problem are considered. Column generation based exact approaches are developed for those problems where the auxiliary problem is solved by a two-level approach comprising a genetic algorithm and an integer linear programming formulation. The genetic algorithm takes advantage of the auxiliary problem structure and appears to be very efficient at providing the master problem with attractive columns. The auxiliary problem integer linear programming (ILP) formulation is then mostly used for proving the optimality status of the current master problem solution. The proposed approaches are shown to be significantly faster than column generation approaches relying only on the auxiliary problem ILP formulation.     

A Branch-and-price algorithm for placement routing for a multi-head beam-type component placement tool

We develop a branch-and-price procedure for a placement routing problem for a multi-head beam-type component placement tool. The problem is modelled as an integer programming model with a huge number of variables, each of which corresponds to a placement route. Its linear programming relaxation is solved by a column generation method. For the column generation subproblem to determine the columns to be added, we develop a dynamic programming procedure. We also propose an effective branching rule to partition the current solution space to eliminate the current fractional solution. Through experiments using real tool data, we observe that the LP relaxation solution value is noticeably close to an integer optimal solution value and hence the integer program formulation and the column generation approach are effective.     

A penalty-based scaling algorithm for the multi-period multi-product distribution planning problem

Multi-period multi-product distribution planning problems are depicted as multi-commodity network flow problems where parameters may change over time. The corresponding mathematical formulation is presented for a discrete time setting, and it can also be used as an approximation for a continuous time setting. A penalty-based method which employs a cost-scaling approach is developed to solve some auxiliary penalty problems aiming to obtain an optimal solution for the original problem. The experiments on both random instances and case study problems show that the algorithm finds good-quality solutions with reasonable computational effort.     

Two-phase approach to GT cell formation using efficient p-median formulations

The purpose of this paper is to develop an efficient p-median approach applicable to large cell formation (CF) problems. A two-phase methodology that seeks to minimize the number of exceptional elements is proposed. In phase I, two efficient p-median formulations which contain fewer binary variables than existing p-median formulations are constructed. For a CF problem with m machines existing p-median formulations contains m² or more binary variables, whereas the new formulation proposed in phase I contains not more than 5m binary variables at the expense of a slightly increased number of continuous variables and constraints for practical values of p less than 32. This makes it possible to implement large CF problem within reasonable computer runtime with commercially available linear integer programming codes. Given the initial cell configuration found with the new p-median formulation, in phase II bottleneck machines and parts are reassigned to reduce the number of exceptional elements. This procedure has the flexibility of providing the cell designer with alternative solutions. Test results on large CF problems show a substantial increase in the efficiency of the new p-median formulations compared with existing p-median formulations.     

Redundancy allocation for series-parallel systems using a max-min approach

The redundancy allocation problem is formulated with the objective of maximizing the minimum subsystem reliability for a series-parallel system. This is a new problem formulation that offers several distinct benefits compared to traditional problem formulations. Since time-to-failure of the system is dictated by the minimum subsystem time-to-failure, a logical design strategy is to increase the minimum subsystem reliability as high as possible, given constraints on the system. For some system design problems, a preferred design objective may be to maximize the minimum subsystem reliability. Additionally, the max-min formulation can serve as a useful and efficient surrogate for optimization problems to maximize system reliability. This is accomplished by sequentially solving a series of max-min subproblems by fixing the minimum subsystem reliability to create a new problem. For this new formulation, it becomes possible to linearize the problem and use integer programming methods to determine system design configurations that allow mixing of functionally equivalent component types within a subsystem. This is the first time the mixing of component types has been addressed using integer programming. The methodology is demonstrated on three problems.     

Machine grouping problem in cellular manufacturing systems— an integer programming approach

In this paper a methodology is proposed to group the machines in cellular manufacturing systems based on the tooling requirements of the parts, toolings available on the machines and the processing times. Two 0-1 integer programming formulations are proposed. These formulations assume that the part families are known. The first formulation groups the machines based on the compatibility of parts with machines. The second formulation groups the machines in order to minimise the cost of allocating the machines and the cost of intercell movement. These formulations take into account the limitations on the number of machines in a group and the number of machines available of a particular type. The application of these formulations is illustrated using an example.     

Cold-standby redundancy optimization for nonrepairable systems

A solution methodology is described and demonstrated to determine optimal design configurations for nonrepairable series-parallel systems with cold-standby redundancy. This problem formulation considers non-constant component hazard functions and imperfect switching. The objective of the redundancy allocation problem is to select from available components and to determine an optimal design configuration to maximize system reliability. For cold-standby redundancy, other formulations have generally required exponential component time-to-failure and perfect switching assumptions. For this paper, there are multiple component choices available for each subsystem and component time-to-failure is distributed according to an Erlang distribution. Optimal solutions are determined based on an equivalent problem formulation and integer programming. Compared to other available algorithms, the methodology presented here more accurately models many engineering design problems with cold-standby redundancy. Previously, it has been difficult to determine optimal solutions for this class of problems or even lo efficiently calculate system reliability. The methodology is successfully demonstrated on a large problem with 14 subsystems.     

A mixed integer linear programming formulation for optimal balancing of mixed-model U-lines

The mixed-model U-line balancing problem was first studied by Sparling and Miltenburg (Sparling, D. and Miltenburg, J., 1998. The mixed-model U-line balancing problem. International Journal of Production Research, 36(2), 485–501) but has not been mathematically formulated to date. This paper presents a mixed integer programming formulation for optimal balancing of mixed-model U-lines. The proposed approach minimises the number of workstations required on the line for a given model sequence. The proposed formulation is illustrated and tested on an example problem and compared with an existing approach. This paper also proposes a new heuristic solution procedure to handle large scale mixed-model U-line balancing problems. A comprehensive experimental analysis is also conducted to evaluate the performance of the proposed heuristic. The results show the validity and usefulness of the proposed integer formulation and effectiveness of the proposed heuristic procedure.     

Distributed optimisation method for multi-resource constrained scheduling in coal supply chains

We consider an integrated planning and scheduling problem motivated by the coal supply chains in Australia. The problem considers production planning of several independent mines. The mines need trains to complete delivery of coal by the arrival of ships at the terminal. The trains, on the other hand, are in limited supply and therefore the mines need to share this common resource. For this problem, we present a mixed integer programming formulation which minimises total weighted earliness, tardiness and operational costs. We also present a distributed algorithm based on the Lagrangian relaxation, which incorporates the volume and Wedelin algorithms. The strength of our distributed algorithm is demonstrated by an extensive computational experiment on several randomly generated instances.     

A general corridor method-based approach for capacitated facility location

The Capacitated Facility Location Problem (CFLP) is a well-known optimisation problem with applications in a number of fields, such as distribution system planning, telecommunication network design, and supply chain design. The goal of this paper is to present a matheuristic algorithm based on the corridor method, to develop a general algorithm for a number of variants of the CFLP. The algorithm exploits solutions obtained via Lagrangean relaxation and builds corridors around such solutions via the introduction of constraints around the incumbent solution, used to limit the size of the solution space explored at each iteration. A thorough exploration of the neighbourhoods induced by the corridors is carried out using a mixed integer programming (MIP) solver. More precisely, we solve to (near) optimality over 500 benchmark instances, using the single-source as well as the multi-source formulations, both in the nominal variant, i.e. the deterministic version of the problem, and the robust variant, i.e. the version obtained when using robust optimisation to model the uncertainty of the problem parameters. The performance of the algorithm is highly competitive when compared with the best approaches proposed in the literature for each variant of the CFLP, especially considering that the algorithm has not been designed with a specific CFLP formulation in mind.     

Scheduling parallel processors: An integer linear programming based heuristic for minimizing setup time

The problem of scheduling parallel processors in a make-to-stock environment with sequence setup costs is considered. A new algorithm which formulates a series of 0-1 integer sub problems is proposed and contrasted with an earlier formulation (Dearing and Henderson 1982,1984). Parallels between the sub problem formulations and generalized networks are discussed. The efficiency and quality of the solutions provided were tested using previously published data for a loom assignment problem. The heuristic solution was evaluated against the optimal integer linear programming (ILP) solution, and a rounded linear program (LP) approximation to the optimal solution for several sample problems. Results indicate that the heuristic is efficient, provides near optimal solutions to production planning problems and requires significantly less computing capability than previously reported LP, TLP approaches.     

Solving the bi-objective optimisation problem with periodic delivery operations using a lexicographic method

Periodic deliveries are typical in a number of real-life applications. Minimising the number of vehicles required to make deliveries to a set of customers with known delivery frequencies is called the problem of vehicle minimisation for periodic deliveries (VMPD). Catering to the welfare of vehicle drivers has now become very important. Consequently, this work integrates the vehicle load balance factor into the VMPD problem by considering both the number of vehicles required to make periodic deliveries and the load balance between vehicles. This work presents integer programming formulations and applies a lexicographic method to this bi-objective VMPD problem. This work also examines whether decomposition can significantly reduce the size and difficulty of basic integer programming formulation in order to output close-to-optimal schedules for large problems within a reasonable computational time. A greedy balancing algorithm is also proposed to use it along with a decomposed integer programming formulation to yield a satisfactory solution in a relatively short time. Computational experiments demonstrate the better competitiveness of the proposed approaches compared to that of the existing approaches.     

An indirect Boundary Element Method for solving low Reynolds number Navier–Stokes equations in a three-dimensional cavity

In the present work, we propose an indirect boundary-only integral equation approach for the numerical solution of the Navier–Stokes system of equations in a three-dimensional flow cavity. The formulation is based on an indirect integral representational formula for the permanent Stokes equations, and the use of a particular solution of a nonhomogeneous Stokes system of equations in order to obtain in an iterative way the corresponding complete solution of the problem. Previous boundary-only integral equation approaches to the present problem, using direct boundary elements formulations, result in a series of matrix multiplications that make these approaches computationally costly. Due to the use of an indirect formulation, the present approach is free from those matrix multiplications. © 1998 John Wiley & Sons, Ltd.