Exact and heuristic procedures for the material handling circular flow path design problem

In this study we develop optimization, decomposition, and heuristic procedures to design a unidirectional loop flow pattern along with the pickup and delivery station locations for unit load automated material handling vehicles. The layout of the facility is fixed, the edges on the boundary of the manufacturing cells are candidates to form the unidirectional loop flow path, and a set of nodes located at an intermediate point on each edge are candidates for pickup and delivery stations of the cell formed by those edges. The objective is to minimize the total loaded and empty vehicle trip distances. The empty vehicle dispatching policy underlying the model is the shortest trip distance first. A binary integer programming model describes the problem of determining the flow path and locations of the pickup and delivery stations in which we then provide a decomposition procedure based on a loop enumeration strategy coupled with a streamlined integer linear programming model. It is shown that only a small proportion of all loops have to be enumerated to reach an optimum. Therefore a truncated version of this algorithm should yield a good heuristic. Finally we propose a neighbourhood search heuristic method and report on its performance.     

Improved formulation,branch-and-cut and tabu search heuristic for single loop material flow system design

The single loop material flow system design is a combinatorial optimization problem, arising in material handling system design, which amounts to designing an unidirectional loop flow pattern as well as to locate pickup and delivery stations. The objective is to minimize the time required to carry out all material flow movements between cells. In this paper, we develop valid inequalities for a previously proposed formulation. The valid inequalities are then embedded into a branch-and-cut framework which is shown to solve much larger instances to optimality than those reported in the literature. A tailored tabu search heuristic is also illustrated and computationally assessed.     

The Vehicle Routing-Allocation Problem: A unifying framework

Summary In this paper the Vehicle Routing-Allocation Problem (VRAP) is presented. In VRAP not all customers need be visited by the vehicles. However customers not visited either have to be allocated to some customer on one of the vehicle tours or left isolated. We concentrate our discussion on the Single Vehicle Routing-Allocation Problem (SVRAP). An integer linear programming formulation of SVRAP is presented and we show how SVRAP provides a unifying framework for understanding a number of the papers and problems presented in the literature. Specifically the covering tour problem, the covering salesman problem, the median tour problem, the maximal covering tour problem, the travelling salesman problem, the generalised travelling salesman problem, the selective travelling salesman problem, the prize collecting travelling salesman problem, the maximum covering/shortest path problem, the maximum population/shortest path problem, the shortest covering path problem, the median shortest path problem, the minimum covering/shortest path problem and the hierarchical network design problem are special cases/variants of SVRAP.     

Network design problem with relays: A genetic algorithm with a path-based crossover and a set covering formulation

The network design problem with relays arises in telecommunications and distribution systems where the payload must be reprocessed at intermediate stations called relays on the route from its origin to its destination. In fiber-optic networks, for example, optical signals may be regenerated several times to overcome signal degradation because of attenuation and other factors. Given a network and a set of commodities, the network design problem with relays involves selecting network edges, determining a route for each commodity, and locating relays to minimize the network design cost. This paper presents a new formulation to the problem based on set covering constraints. The new formulation is used to design a genetic algorithm with a specialized crossover/mutation operator which generates a feasible path for each commodity, and the locations of relays on these paths are determined by solving the corresponding set covering problem. Computational experiments show that the proposed approach can outperform other approaches, particularly on large size problems.     

Optimal and Heuristic Procedures for Row Layout Problems in Automated Manufacturing Systems

In many automated manufacturing environments, particularly flowlines and flexible manufacturing systems (FMSs), machines are arranged along a straight material handling track with a material handling device moving jobs from one machine to aother. These layouts are referred to as row machine layouts. In this paper we study the Row Layout Problem (RLP) under the design objective of minimizing the total backtracking distance of the material handling device, which is a NP-complete problem. We propose the use of a dynamic programming algorithm for its solution. Special cases of the problem, usually encountered in flexible manufacturing cells and which can be solved with polynomial procedures, are also discussed. For the equidistant case (i.e., successive candidate locations are in equal distances), we formulate the problem as an integer linear program. The use of standard mathematical programming codes can efficiently solve this formulation. Two effective heuristic procedures, which explore simple ideas based on local optimality conditions, are also presented. Extensive computational results demonstrate the effectiveness of such heuristics.     

Fleet assignment and routing with schedule synchronization constraints

This paper introduces a new type of constraints, related to schedule synchronization, in the problem formulation of aircraft fleet assignment and routing problems and it proposes an optimal solution approach. This approach is based on Dantzig–Wolfe decomposition/column generation. The resulting master problem consists of flight covering constraints, as in usual applications, and of schedule synchronization constraints. The corresponding subproblem is a shortest path problem with time windows and linear costs on the time variables and it is solved by an optimal dynamic programming algorithm. This column generation procedure is embedded into a branch and bound scheme to obtain integer solutions. A dedicated branching scheme was devised in this paper where the branching decisions are imposed on the time variables. Computational experiments were conducted using weekly fleet routing and scheduling problem data coming from an European airline. The test problems are solved to optimality. A detailed result analysis highlights the advantages of this approach: an extremely short subproblem solution time and, after several improvements, a very efficient master problem solution time.     

An ILP model with logical constraints for mail sorting facility selection

This paper studies a facility selection problem which is generalised from the design of a mail sorting system with multiple input and output. The problem is formulated as a 0–1 integer linear programming (ILP) problem with logical constraints. We show how the logical constraints can be embedded into a ILP model. We compare three strategies for handling logical relations: (1) explicitly as added linear constraints; (2) implicitly as symbolic constraints; and (3) a combination of the two. The effectiveness of computations under different strategies are shown.     

Optimal dynamic routing in Flexible Manufacturing Systems with limited buffers

An optimal routing policy is obtained for Flexible Manufacturing Systems (FMSs) with limited buffers at the work stations. This policy is used to effectively drive a robotic material handling system. The routing decisions are made by a supervising computer on a real-time basis in order to avoid any work station running out of inputs and to control the blocking of the material handling system. Using our model, general material handling times can be assumed. The optimal policy and several key performance measures are computed, following the problem formulation as a continuous-time, semi-Markovian decision process. Fast convergence and computational stability are ensured by the ergodic solution algorithm augmented to solve the functional equations of the renewal process. The solution algorithm was implemented, tested on an extensive range of problems regarding the structure and the performance of the optimal policy. Complex environments involving diverse processing times, as well as very limited buffer storage, were examined. The interaction between the allocation of buffer spaces to work stations, the structural properties of the optimal monotone (threshold-type) policy and the system performance are also investigated.     

Output Regulation in Differential Variational Inequalities using Internal Model Principle and Passivity-Based Approach

We consider the problem of designing state feedback control laws for output regulation in a class of dynamical systems where state trajectories are constrained to evolve within time-varying, closed, and convex sets. The first main result states sufficient conditions for existence and uniqueness of solutions in such systems. We then design a static state feedback control law using the internal model principle, which results in a well-posed closed-loop system and solves the regulation problem. As an application, we demonstrate how control input resulting from the solution of a variational inequality results in regulating the output of the system while maintaining polyhedral state constraints. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An MILP for scheduling problems in an FMS with one vehicle

This paper concerns the mathematical formulation and optimal solutions for the Flexible Manufacturing Systems Scheduling Problem (FMSSP) with one vehicle. This linear formulation differs from the previously published ones as it takes into account the maximum number of jobs allowed in the system, limited input/output buffer capacities, empty vehicle trips and no-move-ahead trips simultaneously. Our objective is to propose optimal solutions for small and medium-sized instances and to examine a number of commonly used assumptions and heuristics. Computational experiments are carried out on instances adapted from Bilge and Ulusoy [Bilge, Ü., Ulusoy, G., 1995. A time window approach to simultaneous scheduling of machines and material handling system in an FMS. Operations Research 43, 1058–1070] and the following heuristics are evaluated: FIFO (First In First Out) rules for input/output buffer management; and FIFO, SPT (Shortest Processing Time), STT (Shortest Travel Time) and MOQS (Maximum Outgoing Queue Size) rules concerning the vehicle. The consequences of classical assumptions are also studied: ignoring empty trips, ignoring no-move-ahead constraints, and ignoring vehicle-disjunction constraints. The numerical experiments provide a set of optimal solutions and allow to evaluate the performances of heuristic search schemes.     

The maximum covering/shortest path problem: A multiobjective network design and routing formulation

In this paper the authors introduce the maximum covering/shortest path problem and the maximum population/shortest path problem, a special case of the former model. Both models are formulated as two objective integer programs. A summary of the results of a sample problem for the latter formulation is given. Possible modifications to, and extensions and applications of both models are also presented. With these formulations the authors extend the concept of ‘coverage’ from facility location analysis to network design and routing analysis.     

Subgradient optimization applied to a discrete nonlinear problem in engineering design

The particular application considered here is the design of relief-header systems, involving compressible fluid flow through tree-networks. The flowrates are specified, and the design problem involves the choice of discrete pipe sizes to minimize total cost while satisfying pressure-drop constraints, which are highly nonlinear. The problem is solved in two stages. Firstly the problem of obtaining the optimal set of continuous pipe sizes is addressed; it turns out that a dual formulation provides and extremely rapid solution. Next, a subgradient optimization procedure is used on the dual in order to solve for the discrete pipe sizes. Networks of up to 78 paths and 205 sections, each involving 50 discrete pipe sizes, have been solved.     

On the formulation of stochastic linear programs using algebraic modelling languages

This paper considers extensions to algebraic modelling languages to support formulation, instantiation and solver integration for stochastic linear programs (SLPs). We present a taxonomy of SLP problem types and analyze formulation requirements including distribution handling by class of problem. We demonstrate suggested formulations for most problem classes, show solver input in the S-MPS standard, and propose consistency checks for constraints involving stochastic data items. Some unresolved difficulties are identified.     

Integrated production and material handling scheduling using mathematical programming and constraint programming

In this article, we propose an integrated formulation of the combined production and material handling scheduling problems. Traditionally, scheduling problems consider the production machines as the only constraining resource. This is however no longer true as material handling vehicles are becoming more and more valuable resources requiring important investments. Their operations should be optimized and above all synchronized with machine operations. In the problem addressed in this paper, a job shop context is considered. Machines and vehicles are both considered as constraining resources. The integrated scheduling problem is formulated as a mathematical programming model and as a constraint programming model which are compared for optimally solving a series of test problems. A commercial software (ILOG OPLStudio) was used for modeling and testing both models.     

An origin-based model for unique shortest path routing

Link weights are the main parameters of shortest path routing protocols, the most commonly used protocols for IP networks. The problem of optimally setting link weights for unique shortest path routing is addressed. Due to the complexity of the constraints involved, there exist challenges to formulate the problem in such a way based on which a more efficient solution algorithm than the existing ones may be developed. In this paper, an exact formulation is first introduced and then mathematically proved correct. It is further illustrated that the formulation has advantages over a prior one in terms of both constraint structure and model size for a proposed decomposition method to solve the problem.     

Optimal design of a manpower system

An equilibrium model of a manpower system is developed based on the notion of a career flow. Institutional constraints and measures of system performance are linear functions of the career flow. A typical optimal design problem is formulated and a solution procedure is developed. The optimization problem is a generalized linear program in which columns are generated by solving a shortest path problem. Upper and lower bounds on the optimal value function can be developed at each stage of the calculations.This research was supported by ONR grant N00014-75-C-0619.     

An ant colony system for enhanced loop-based aisle-network design

The purpose of this paper is to develop a global optimization model, simplification schemes, and a heuristic procedure for the design of a shortcut-enhanced unidirectional loop aisle-network with pick-up and drop-off stations. The objective is to minimize the total loaded and empty trip distances. This objective is the main determinant for the fleet size of the vehicles, which in turn is the driver of the total life-cycle cost of vehicle-based unit-load transport systems. The shortcut considerably reduces the length of the trips while maintaining the simplicity of the system. The global model solves simultaneously for the loop design, stations’ locations and shortcut design. We then develop two simplifications each containing two serial phases. Phase-1 of the first simplification step focuses on both loaded and empty trips, while that of the second simplification focuses only on loaded trips. In phase-2, both designs are enhanced with a shortcut to minimize both loaded and empty trip distances. The quality and efficiency of the three alternative designs are tested for a set of problems with different layout size and product mix. While the solution time of the second simplification procedure is a small percentage of the global formulation, it generates satisfactory solutions. On this foundation, we then develop a heuristic procedure to replace phase-1 of the second simplification. The heuristic procedure is using ant colony system to generate feasible solutions and then we implement a local search algorithm to improve the results. The heuristic algorithm quickly generates close to optimal solutions for phase-1 of the second simplification. By applying phase-2 of the this second simplification on a set of loops generated by the heuristic, close to optimal solutions are also quickly obtained for the global model.     

Analysis of a Fork/Join Synchronization Station with Inputs from Coxian Servers in a Closed Queuing Network

Fork/join stations are commonly used to model the synchronization constraints in queuing models of computer networks, fabrication/assembly systems and material control strategies for manufacturing systems. This paper presents an exact analysis of a fork/join station in a closed queuing network with inputs from servers with two-phase Coxian service distributions, which models a wide range of variability in the input processes. The underlying queue length and departure processes are analyzed to determine performance measures such as throughput, distributions of the queue length and inter-departure times from the fork/join station. The results show that, for certain parameter settings, variability in the arrival processes has a significant impact on system performance. The model is also used to study the sensitivity of performance measures such as throughput, mean queue lengths, and variability of inter-departure times for a wide range of input parameters and network populations.     

Applications of mathematical programming models

A sizeable proportion of manufacturing expenses can be attributed to facility layout and material handling. Facility layout decisions involve designing the arrangement of elements in manufacturing systems. Among the most critical material handling decisions in this area are the arrangement and design of material flow patterns. This survey article reviews loop based facility planning and material handling decisions for trip based material handling equipment with an emphasis on unit load automated guided vehicles. The article examines issues related with facility design, material handling design, and fleet sizing and operating.     

Robust berth scheduling with uncertain vessel delay and handling time

In container terminals, the actual arrival time and handling time of a vessel often deviate from the scheduled ones. Being the input to yard space allocation and crane planning, berth allocation is one of the most important activities in container terminals. Any change of berth plan may lead to significant changes of other operations, deteriorating the reliability and efficiency of terminal operations. In this paper, we study a robust berth allocation problem (RBAP) which explicitly considers the uncertainty of vessel arrival delay and handling time. Time buffers are inserted between the vessels occupying the same berthing location to give room for uncertain delays. Using total departure delay of vessels as the service measure and the length of buffer time as the robustness measure, we formulate RBAP to balance the service level and plan robustness. Based on the properties of the optimal solution, we develop a robust berth scheduling algorithm (RBSA) that integrates simulated annealing and branch-and-bound algorithm. To evaluate our model and algorithm design, we conduct computational study to show the effectiveness of the proposed RBSA algorithm, and use simulation to validate the robustness and service level of the RBAP formulation.