Search

In the e-commerce era, efficient order fulfillment processes in distribution centers have become a key success factor. One novel technology to streamline these processes is robot-assisted order picking. In these systems, human order pickers are supported by autonomous mobile robots (AMRs), which carry bins for collecting picking orders, autonomously move through the warehouse, and wait in front of a shelf containing a requested stock keeping unit (SKU). Once a picker has approached a waiting AMR and placed the requested SKU into the respective bin, AMR and picker may separate and move toward other picking positions. In this way, pickers continuously move between different waiting AMRs without having to return to the depot. This paper treats the coordination of multiple AMRs and multiple pickers to minimize the makespan. We present a heuristic method for the deterministic case that can handle the requirements of large e-commerce fulfillment centers and successfully solves instances with more than one thousand picking positions. Based on the obtained solutions, the performance of our picking system is compared with the traditional warehouse setup without AMR support and to another work policy using fixed pairings of picker and AMR per order. We find that largely improved makespans can be expected. In addition, we analyze the effects of stochastic picking times, speed differences between AMRs and pickers, and a zoning strategy. The ripple effect caused by stochastic picking times, in which a single delay may cascade through a tightly synchronized schedule and deteriorate picking performance, can be effectively mitigated by separating the workforce into smaller subgroups. Another important finding is that pickers and AMR should have approximately the same travel speed because slower AMRs deteriorate system performance. Finally, zoning slightly decreases the flexibility of the system and should be used if dictated by organizational reasons. History: This paper has been accepted for the Transportation Science Special Issue on Emerging Topics in Transportation Science and Logistics. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.1207. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the one-machine scheduling problem with release and delivery times with the minimum makespan objective. Both heuristics and branch-and-bound algorithms have been formulated for the problem. One such branch-and-bound algorithm solves the problem and a variation that requires a delay between the completion of one job and the start of another (delayed precedence constraints). This paper analyzes key components of this branch-and-bound algorithm and proposes an improved heuristic to be used in conjunction with a different search strategy. Computational experiments demonstrate that the modifications lead to substantial improvements in running time and number of iterations on the one-machine problem instances both with and without delayed precedence constraints. [ABSTRACT FROM AUTHOR]

We investigate the discrete parallel machine scheduling and location problem, which consists of locating multiple machines to a set of candidate locations, assigning jobs from different locations to the located machines, and sequencing the assigned jobs. The objective is to minimize the maximum completion time of all jobs, that is, the makespan. Though the problem is of theoretical significance with a wide range of practical applications, it has not been well studied as reported in the literature. For this problem, we first propose three new mixed-integer linear programs that outperform state-of-the-art formulations. Then, we develop a new logic-based Benders decomposition algorithm for practical-sized instances, which splits the problem into a master problem that determines machine locations and job assignments to machines and a subproblem that sequences jobs on each machine. The master problem is solved by a branch-and-cut procedure that operates on a single search tree. Once an incumbent solution to the master problem is found, the subproblem is solved to generate cuts that are dynamically added to the master problem. A generic no-good cut is first proposed, which is later improved by some strengthening techniques. Two optimality cuts are also developed based on optimality conditions of the subproblem and improved by strengthening techniques. Numerical results on small-sized instances show that the proposed formulations outperform state-of-the-art ones. Computational results on 1,400 benchmark instances with up to 300 jobs, 50 machines, and 300 locations demonstrate the effectiveness and efficiency of the algorithm compared with current approaches. Summary of Contribution: This paper employs operations research methods and computing techniques to address an NP-hard combinatorial optimization problem: the parallel discrete machine scheduling and location problem. The problem is of practical significance but has not been well studied in the literature. For the problem, we formulate three novel mixed-integer linear programs that outperform state-of-the-art formulations and develop a new logic-based Benders decomposition algorithm. Extensive computational experiments on 1,400 benchmark instances with up to 300 jobs, 50 machines, and 300 locations are conducted to evaluate the performance of the proposed models and algorithms. [ABSTRACT FROM AUTHOR]

The β-robust machine scheduling has attracted increasing attention as an effective method to hedge against uncertainty. However, existing β-robust scheduling models rely on the normality assumption of uncertain parameters, and existing solution methods are based on branch and bound, which cannot solve problems of 45 jobs within 3,600 seconds. This paper proposes distributionally β-robust scheduling (DRS) models to handle uncertain processing times. The DRS models only require the lower bound, mean, and covariance information of processing times, and have the capability of handling both single and parallel machine problems. Another key contribution of this paper is to devise efficient parametric search (PS) methods for the DRS models. Specifically, we show that there exists a parameterized assignment problem (PAP), such that its optimal solutions are also optimal for the original problem. The proposed methods only need to perform a onedimensional PS and solve a series of PAPs.We further propose a bidirectional PS to reduce the number of PAPs needed to be solved, and we design a speedup shortest augmentation path algorithm for these PAPs. Experimental results on both single and identical parallel machine problems show that the improved PS method outperforms existing algorithms by more than three orders of magnitude improvement in computation time for problems of 45 jobs, and it is able to solve problems of 500 jobs within 0.5 seconds. [ABSTRACT FROM AUTHOR]

This paper describes how static task-scheduling methods using stochastic search techniques can be applied to digital systems that are composed entirely of reconfigurable hardware. Such reconfigurable hardware is characterized by the property that its low-level logical functionality is not determined at the time of manufacture, but rather that this functionality becomes set only shortly before or during the invocation of the targeted application. The purpose of this paper is to introduce the basic framework for applying static scheduling theory to arbitrarily-structured task systems targeted to be implemented in prefabricated resource-constrained reconfigurable hardware. The paper also describes initial solutions to this heterogeneous task-scheduling problem that combine a distributed list-based scheduling technique with three probabilistic search strategies. The techniques introduced produce detailed task scheduling and high-level hardware configuration information that can serve as inputs to the software and reconfigurable hardware design automation tools used in the hardware/software codesign process. [ABSTRACT FROM AUTHOR]

Insertion heuristics have proven to be popular methods for solving a variety of vehicle routing and scheduling problems. In this paper, we focus on the impact of incorporating complicating constraints on the efficiency of insertion heuristics. The basic insertion heuristic for the standard vehicle routing problem has a time complexity of O(n³). However, straightforward implementations of handling complicating constraints lead to an undesirable time complexity of O(n4. We demonstrate that with careful implementation it is possible, in most cases, to maintain the O⊃3 complexity or, in a few cases, increase the time complexity to O(n⊃3 log n). The complicating constraints we consider in this paper are time windows, shift time limits, variable delivery quantities, fixed and variable delivery times, and multiple routes per vehicle. Little attention has been given to some of these complexities (with time windows being the notable exception), which are common in practice and have a significant impact on the feasibility of a schedule as well as the efficiency of insertion heuristics. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to introduce a new test-problem collection for stochastic linear programming that the authors have recently begun to assemble. While there are existing stochastic programming test-problem collections, our new collection has three features that distinguish it from existing collections. First, our collection is web-based with free public access, and we intend to enrich it as new test problems become available. Indeed, we encourage submissions of new test problems. Second, along with the collection we provide documentation of the problems, so that researchers can quickly find information about each family without reading through the original source. Third, all of the data in our collection are provided in SMPS (Birge et al. 1987, Gassmann and Schweitzer 2001) format. In this paper, we provide an introduction to the stochastic linear program, give a brief description of each problem family currently in the test-problem collection, and describe the documentation that accompanies the collection. [ABSTRACT FROM AUTHOR]

The objective of this paper is to review the current status of ship routing and scheduling. We focus on literature published during the last decade. Because routing and scheduling problems are closely related to many other fleet planning problems, we have divided this review into several parts. We start at the strategic fleet planning level and discuss the design of fleets and sea transport systems. We continue with the tactical and operational fleet planning level and consider problems that comprise various ship routing and scheduling aspects. Here, we separately discuss the different modes of operations: industrial, tramp, and liner shipping. Finally, we take a glimpse at naval applications and other related problems that do not naturally fall into these categories. The paper also presents some perspectives regarding future developments and use of optimization-based decision-support systems for ship routing and scheduling. Several of the trends indicate both accelerating needs for and benefits from such systems and, hopefully, this paper will stimulate further research in this area. [ABSTRACT FROM AUTHOR]

This paper presents two new models to deal with different tooling requirements in the generic multipleproduct assembly-system design (MPASD) problem and proposes a new branch-and-cut solution approach, which adds cuts at each node in the search tree. It employs the facet generation procedure (FGP) to generate facets of underlying knapsack polytopes. In addition, it uses the FGP in a new way to generate additional cuts and incorporates two new methods that exploit special structures of the MPASD problem to generate cuts. One new method is based on a principle that can be applied to solve generic 0-1 problems by exploiting embedded integral polytopes. The approach includes new heuristic and pre-processing methods, which are applied at the root node to manage the size of each instance. This paper establishes benchmarks for MPASD through an experiment in which the approach outperformed IBM's Optimization Subroutine Library (OSL), a commercially available solver. [ABSTRACT FROM AUTHOR]

In-plant railroad engine scheduling involves routing and scheduling decisions for a heterogeneous fleet of switching engines to serve a set of time-window and capacity-constrained transportation requests. Despite an ever-increasing competition, the current planning is purely by pencil and paper. Our paper describes the mathematical and algorithmic developments for addressing in-plant railroad decision support for scheduling and routing. The problem discussed in our work is related to the multiple-vehicle pickup and delivery problem. Exploiting the structure of admissible schedules of our particular railroad situation, we introduce two formulations of the problem as mixed integer and set partitioning programs. We propose solving the linear programming relaxation of the set partition model by column generation. We focus on the pricing problem stated in the form of a constrained shortest path problem, which is 33 complete in the strong sense. A new exact label correcting algorithm is developed that prunes the search space in a novel manner. Heuristically obtained integer solutions of a practical quality are proposed as well. All the claims are demonstrated by computational experiments on both artificial and real-life data. We discuss implementation details as well. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of finding the minimum number of vehicles required to visit a set of nodes subject to time window and capacity constraints. The fleet is homogeneous and is located at a common depot. Each node requires the same type of service. An exact method is introduced based on branch and cut. In the computations, ever increasing lower bounds on the optimal solution are obtained by solving a series of relaxed problems that incorporate newly found valid inequalities. Feasible solutions or upper bounds are obtained with the help of greedy randomized adaptive search procedure (GRASP). A wide variety of cuts is introduced to tighten the linear programming (LP) relaxation of the original mixed-integer program. To find violated cuts, it is necessary to solve a separation problem. A substantial portion of the paper is aimed at describing the heuristics developed for this purpose. A new approach for obtaining feasible solutions from the LP relaxation is also discussed. Numerical results for standard 50- and 100-node benchmark problems are reported. [ABSTRACT FROM AUTHOR]

This paper addresses the assembly-line scheduling problem with concurrent operations per stage and parallel machines.This problem can be brie .y described as the problem of sequencing a predetermined set of parts with known processing-time requirements through an r -station assembly line so that the makespan is minimized.A set of concurrent operations must be performed at each station on each part.This set of operations is usually part- dependent since different parts have different processing requirements.In this paper,we construct schedules in quadratic time for this strongly NP-hard problem with an abso- lute performance guarantee independent of the number of jobs.This makes our schedules asymptotically optimal as the number of jobs becomes very large.The implementation of our schedules facilitates the ef .cient use of concurrent operations and prevents the assem- bly line from degenerating into performing operations serially,which would result in low production rates.We utilize compact vector summation techniques and .rst construct a schedule for the case where each concurrent operation is performed by a single machine. We then generalize our schedule to the case where each concurrent operation is performed by a set of identical parallel machines. [ABSTRACT FROM AUTHOR]

Vehicle scheduling is the process of assigning vehicles to a set of predetermined trips with fixed starting and ending times, while minimizing capital and operating costs. This paper considers modeling, algorithmic, and computational aspects of the polynomially solvable case in which there is a single depot and vehicles are identical. A quasiassignment formulation is reviewed and an alternative asymmetric assignment formulation is given. The main contributions of the paper area new two-phase approach which is valid in the case of a special cost structure, an auction algorithm for the quasiassignment problem, a core-oriented approach, and an extensive computational study. New algorithms are compared with the most successful algorithms for the vehicle-scheduling problem, using both randomly generated and real-life data. The new algorithms show a significant performance improvement with respect to computation time. Such improvement can, for example, be very important when this particular vehicle-scheduling problem appears as a subproblem in more complex vehicle- and crew-scheduling problems. [ABSTRACT FROM AUTHOR]

This paper discusses the application of neural networks to select the best heuristic algorithm to solve a given scheduling problem. The two-stage hybrid flowshop with multiple identical parallel machines at the second stage is used as an example to discuss the process of selecting a scheduling heuristic through a neural-network approach. This paper uses the genetic-algorithm-based approach for training the neural network and shows that the suggested neural-network approach is quite effective and efficient for selecting the best heuristic algorithm for solving a given scheduling problem. [ABSTRACT FROM AUTHOR]

Recently, Daganzo introduced the cell transmission model--a simple approach for modeling highway traffic flow consistent with the hydrodynamic model. In this paper, we use the cell transmission model to formulate the single destination System Optimum Dynamic Traffic Assignment (SO DTA) problem as a Linear Program (LP). We demonstrate that the model can obtain insights into the DTA problem, and we address various related issues, such as the concept of marginal travel time in a dynamic network and system optimum necessary and sufficient conditions. The model is limited to one destination and, although it can account for traffic realities as they are captured by the cell transmission model, it is not presented as an operational model for actual applications. The main objective of the paper is to demonstrate that the DTA problem can be modeled as an LP, which allows the vast existing literature on LP to be used to better understand and compute DTA. A numerical example illustrates the simplicity and applicability of the proposed approach. [ABSTRACT FROM AUTHOR]

This paper presents an efficient algorithm for an integrated operating room planning and scheduling problem. It combines the assignment of surgeries to operating rooms and scheduling over a short-term planning horizon. This integration results in more stable planning through consideration of the operational details at the scheduling level, and this increases the chance of successful implementation. We take into account the maximum daily working hours of surgeons, prevent the overlapping of surgeries performed by the same surgeon, allow time for the obligatory cleaning when switching from infectious to noninfectious cases, and respect the surgery deadlines. We formulate the problem using a mathematical programming model and develop a branch-and-price-and-cut algorithm based on a constraint programming model for the subproblem. We also develop dominance rules and a fast infeasibility-detection algorithm based on a multidimensional knapsack problem to improve the efficiency of the constraint programming model. The computational results show that our method has an average optimality gap of 2.81% and significantly outperforms a compact mathematical formulation in the literature. [ABSTRACT FROM AUTHOR]

In this paper, we study a scheduling problem on a single machine, provided that the jobs have individual release dates and deadlines, and the processing times are controllable. The objective is to find a feasible schedule that minimizes the total cost of reducing the processing times. We reformulate the problem in terms of maximizing a linear function over a submodular polyhedron intersected with a box. For the latter problem of submodular optimization, we develop a recursive decomposition algorithm and apply it to solving the single machine scheduling problem to achieve the best possible running time. [ABSTRACT FROM AUTHOR]

This paper explores some of the traffic phenomena that arise when drivers have to navigate a network in which queues back up past diverge intersections. If a diverge provides two alternative routes to the same destination and the shorter route has a bottleneck that generates a queue, one would expect that queue to stabilize at an equilibrium level where the travel time on both routes is roughly equal. If the capacity of the alternative route is unlimited then this network can accommodate any demand level. However, if the bottleneck is so close to the upstream end of the link that the equilibrium queue cannot be contained in the link, then the trip time on the queued route cannot grow to match that on the alternate route. This means that the alternative route can never be attractive, even if the queue spills back past the diverge, and that drivers approaching the diverge will act as if the alternative route did not exist. As a result, a steady flow into the system greater than the capacity of the bottleneck will cause a queue to grow all the way back to the origin (blocking it). The final result is an "oversaturated static state" where the queue regulates the input flow into the system. Curiously, if the bottleneck capacity of this network is reduced below a critical level (or is eliminated altogether) then the alternative route becomes attractive again and the system cannot reach the saturation point. This phenomenon is explored in the paper, where it is also shown that: i) a network can become permanently oversaturated / undersaturated as a result of a temporary increase / decrease in link capacity, ii) even under the most favorable assumptions, and in contrast to the equivalent assignment problem with point queues, a network can be stable both in an oversaturated and an undersaturated state, and iii) temporary endogenous disturbances can permanently reverse the saturation state of a network. These findings suggest that in certain situations the time-dependent traffic assignment problem with physical queues is chaotic in nature and that (as in weather forecasting) it may be impossible to obtain input data with the required accuracy to make reliable predictions of cumulative output flows. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of routing trains through railway stations. This problem occurs as a subproblem in a project which the authors are carrying out in cooperation with the Dutch railways. The project involves the analysis of future infrastructural capacity requirements in the Dutch railway network, Part of this project is the automatic generation and evaluation of timetables. To generate a timetable a hierarchical approach is followed: at the upper level in the hierarchy a tentative timetable is generated, taking into account the specific scheduling problems of the trains at the railway stations at an aggregate level. At the lower level in the hierarchy it is checked whether the tentative timetable is feasible with respect to the safety rules and the connection requirements at the stations. To carry out this consistency cheek, detailed schedules for the trains at the railway yards have to be generated. In this paper we present a mathematical model formulation for this detailed scheduling problem, based on the Node Packing Problem (NPP). Furthermore, we describe a solution procedure for the problem, based on a branch-and-cut approach. The approach is tested in an empirical study with data from the station of Zwolle in The Netherlands. [ABSTRACT FROM AUTHOR]

This paper addresses the development of effective heuristics for solving the vehicle routing and scheduling problem with time window constraints. Both tour construction and local search tour improvement heuristics are developed. A major premise of the paper is that embedding global tour improvement procedures within the tour construction process can lead to improved solutions. Computational results are reported on test problems from the literature as well as real world applications. The hybrid construction / improvement heuristic is more effective in reducing vehicle fleet size requirements than previously reported heuristics. [ABSTRACT FROM AUTHOR]

A substantial literature exists on the estimation of the delay function for a single-track railroad with the assumption that the trains are uniformly distributed over time. In order to make the estimation more accurate and realistic, this paper provides the definition of delay functions for a scheduled railroad in which each train has a scheduled departure and arrival time. The key feature of this paper is that the uncertainty in the actual train departure time is explicitly taken into consideration. Since the variance of delay is important in the measurement of the reliability of a given set of schedules, both the mean and the variance of delay are estimated by solving a system of nonlinear equations. [ABSTRACT FROM AUTHOR]

This paper extends the results of a previous study concerning distribution with time windows. It is recognized that customers who do not need to be allocated to a time window should receive different service than the rest. Three strategies were studied to accomplish that: stratified service, discriminating service, and staggered and discriminating service. Of these, the last strategy yields the lowest local distribution distance per customer, a distance which can be less than hall that for the strategy explained in the previous paper (joint service). Stratified service, however, can yield a lower line-haul distance per customer than staggered and discriminating service. In a specific case, a numerical comparison between stratified service and staggered and discriminating service should determine the overall best choice. This choice notwithstanding, the best strategy involves overlapping vehicle tours. The conventional wisdom of dividing customers into non-overlapping clusters for vehicle muting does not seem attractive for distribution problems with time windows. [ABSTRACT FROM AUTHOR]

This paper shows how distribution problems with delivery time constraints can be modeled approximately with just a few variables. Its objective is neither to develop a scheduling algorithm nor an exact predictive method; rather, it is to illustrate some trade-offs and principles that can be used for planning and algorithm development. A workday is divided into time periods. Time windows are modeled by specifying the period in which a vehicle should visit each customer. (The companion paper explores scenarios where many customers do not specify a time window, and thus, it is advantageous not to allocate all the customers to periods.) Travel distance expressions are provided for a "cluster-first, route-second" strategy, similar to some routing methods currently in use. Travel distance expressions are also provided for refinements of the strategy, including one in which tours are systematically staggered, overlapping. The consequent reductions in travel distance can be quite significant. We suggest here that more attention should be paid to the clustering part of algorithm construction, and point to ways in which the customers served by one vehicle should be selected. This paper shows how distribution problems with delivery time constraints can be modeled approximately with just a few variables. Its objective is neither to develop a scheduling algorithm nor an exact predictive method; rather, it is to illustrate some trade-offs and principles that can be used for planning and algorithm development. A workday is divided into time periods. Time windows are modeled by specifying the period in which a vehicle should visit each customer. (The companion paper explores scenarios where many customers do not specify a time window, and thus, it is advantageous not to allocate all the customers to periods.) Travel distance expressions are provided for a "cluster-first, route-second" strategy, similar to some routing methods currently in use. Travel distance expressions are... [ABSTRACT FROM AUTHOR]

This paper develops and evaluates a simple model for scheduling vehicle arrivals at transportation terminals where vehicles are randomly delayed en route. Equations are developed for the optimal "slack" time (the time between the scheduled arrival for a feeder line and the scheduled departure for a transfer line) when vehicles are delayed according to an exponential probability distribution. These equations only depend on the average vehicle delay and the tine headway on the transfer line. The paper shows that coordinating arrivals with departures is most important when the headway is large relative to average vehicle delay. [ABSTRACT FROM AUTHOR]

In this paper, a new procedure for the routing and scheduling of school buses is presented. This procedure has been implemented and tested successfully in two school districts. It resulted in about a 20% savings in cost in one of these districts and the transportation of 600 additional students with one extra bus in the second. Also, in this paper, the key aspects of the procedures for the preparation of the data are explained including the ministop concept, a new and innovative method for the coding of the network data. In each section of this paper, the core algorithm is explained, followed by the modifications that were made in attempting to implement the theoretical procedure. In this way, the contract between theory and practice can be shown. [ABSTRACT FROM AUTHOR]

We introduce a simple technique for disjunctive machine scheduling problems and show that this method can match or even outperform state-of-the-art algorithms on a number of problem types. Our approach combines a number of generic search techniques such as restarts, adaptive heuristics, and solution-guided branching on a simple model based on a decomposition of disjunctive constraints and on the reification of these disjuncts. This paper describes the method and its application to variants of the job shop scheduling problem (JSP). We show that our method can easily be adapted to handle additional side constraints and different objective functions, often outperforming the state-of-the-art and closing a number of open problems. Moreover, we perform in-depth analysis of the various factors that make this approach efficient. We show that, while most of the factors give moderate benefits, the variable and value ordering components are key. [ABSTRACT FROM AUTHOR]

Scheduling elective procedures in an operating suite is a formidable task because of competing performance metrics and uncertain surgery durations. In this paper, we present an optimization framework for batch scheduling within a block booking system that maximizes the expected utilization of operating room resources subject to a set of probabilistic capacity constraints. The algorithm iteratively solves a series of mixed-integer programs that are based on a normal approximation of cumulative surgery durations. This approximation is suitable for high-volume medical specialities but might not be acceptable for the specialties that perform few procedures per block. We test our approach using the data from the ophthalmology department of the Veterans Affairs Pittsburgh Healthcare System. The performance of the schedules obtained by our approach is significantly better than schedules produced by simple heuristic scheduling rules. [ABSTRACT FROM AUTHOR]

This paper presents an optimal constraint programming approach for the open-shop scheduling problem, which integrates recent constraint propagation and branching techniques with new upper bound heuristics. Randomized restart policies combined with nogood recording allow us to search diversification and learning from restarts. This approach is compared with the best-known metaheuristics and exact algorithms, and it shows better results on a wide range of benchmark instances. [ABSTRACT FROM AUTHOR]

Traditionally, the airline crew scheduling problem has been decomposed into a crew pairing problem and a crew assignment problem, both of which are solved sequentially. The first consists of generating a set of least-cost crew pairings (sequences of flights starting and ending at the same crew base) that cover all flights. The second aims at finding monthly schedules (sequences of pairings) for crew members that cover all pairings previously built. Pairing and schedule construction must respect all safety and collective agreement rules. In this paper, we focus on the pilot crew scheduling problem in a bidline context where anonymous schedules must be built for pilots and high fixed costs are considered to minimize the number of scheduled pilots. We propose a model that completely integrates the crew pairing and crew assignment problems, and we develop a combined column generation/dynamic constraint aggregation method for solving them. Computational results on real-life data show that integrating crew pairing and crew assignment can yield significant savings-on average, 3.37% on the total cost and 5.54% on the number of schedules for the 7 tested instances. The integrated approach, however, requires much higher computational times than the sequential approach. [ABSTRACT FROM AUTHOR]

The generalized vehicle routing problem (GVRP) consists of finding a set of routes for a number of capacitated vehicles on a graph where the vertices are partitioned into clusters with given demands, such that the total cost of travel is minimized and all demands are met. This paper describes and compares four new integer linear programming formulations for the GVRP, two based on multicommodity flow and the other two based on exponential-size sets of inequalities. Branch-and-cut algorithms are proposed for the latter two. Computational results on a large set of instances are presented. [ABSTRACT FROM AUTHOR]

In open railway markets, coordinating train schedules at an interchange station requires negotiation between two independent train-operating companies to resolve their operational conflicts. This paper models the stakeholders as software agents and proposes an agent negotiation model to study their interaction. Three negotiation strategies have been devised to represent the possible objectives of the stakeholders, and they determine the behavior of the stakeholders in proposing offers to other stakeholders. Empirical simulation results confirm that the use of the proposed negotiation strategies lead to outcomes that are consistent with the objectives of the stakeholders. [ABSTRACT FROM AUTHOR]

The paper investigates train scheduling problems when prioritised trains and nonprioritised trains are simultaneously traversed in a single-line rail network. In this case, no-wait conditions arise because the prioritised trains such as express passenger trains should traverse continuously without any interruption. In comparison, nonprioritised trains such as freight trains are allowed to enter the next section immediately if possible or to remain in a section until the next section on the routing becomes available, which is thought of as a relaxation of no-wait conditions. With thorough analysis of the structural properties of the No-Wait Blocking Parallel- Machine Job-Shop Scheduling (NWBPMJSS) problem that is originated in this research, an innovative generic constructive algorithm (called NWBPMJSS¯Liu-Kozan) is proposed to construct the feasible train timetable in terms of a given order of trains. In particular, the proposed NWBPMJSS¯Liu-Kozan constructive algorithm comprises several recursively used subalgorithms (i.e., Best-Starting-Time-Determination Procedure, Blocking- Time-Determination Procedure, Conflict-Checking Procedure, Conflict-Eliminating Procedure, Tune-Up Procedure, and Fine-Tune Procedure) to guarantee feasibility by satisfying the blocking, no-wait, deadlock-free, and conflict-free constraints. A two-stage hybrid heuristic algorithm (NWBPMJSS¯Liu-Kozan-BIH) is developed by combining the NWBPMJSS¯Liu-Kozan constructive algorithm and the Best-Insertion-Heuristic (BIH) algorithm to find the preferable train schedule in an efficient and economical way. Extensive computational experiments show that the proposed methodology is promising because it can be applied as a standard and fundamental toolbox for identifying, analysing, modelling, and solving real-world scheduling problems. [ABSTRACT FROM AUTHOR]

The airline industry currently has a $40-billion plus market and is expected to grow rapidly with the population growth and growth in the overall economy. Everyday, thousands of aircrafts undergo maintenance, repair, and overhaul. The aircraft maintenance problem is one of the important logistic problems in the airline industry. It is aimed at scheduling the aircrafts' routing so that enough maintenance opportunities are provided to every aircraft in the fleet. In this paper, we present a new compact network representation of the aircraft maintenance routing problem (AMR) and propose a new mixed-integer linear programming formulation to solve the problem. The quality of this model was assessed on four real test instances from a major U.S. carrier, and compared with the flight string model proposed in the literature. The computational results show that the proposed model is able to obtain the optimal solutions to all test instances in reasonable time. This study suggests that this model can be applied to integrated problems of the AMR and other planning problems such as the fleet assignment problem and crew pairing problem. [ABSTRACT FROM AUTHOR]

The cell-transmission model-based single-destination system optimal dynamic traffic assignment problem proposed by Ziliaskopoulos was mostly solved by standard linear programming (LP) methods, e.g., simplex and interior point methods, which produce link-based flows involving vehicle-holding phenomenon. In this paper we present a network flow algorithm for this problem. We show that the problem is equivalent to the earliest arrival flow and then solve the earliest arrival flow on a time-expanded network. In particular, a scaled flow scheme is proposed to deal with the situation in which the ratio of backward wave speed to forward wave speed is less than one. The proposed algorithm produces path-based flows exhibiting realistic nonvehicle-holding properties. Complexity and numerical analyses show that the algorithm runs more efficiently than LP. [ABSTRACT FROM AUTHOR]

This paper introduces a new variant of the one-to-many-to-one single vehicle pickup and delivery problems (SVPDP) that incorporates the handling cost incurred when rearranging the load at the customer locations. The simultaneous optimization of routing and handling costs is difficult, and the resulting loading patterns are hard to implement in practice. However, this option makes economical sense in contexts where the routing cost dominates the handling cost. We have proposed some simplified policies applicable to such contexts. The first is a two-phase heuristic in which the tour having minimum routing cost is initially determined by optimally solving an SVPDP, and the optimal handling policy is then determined for that tour. In addition, branch-and-cut algorithms based on integer linear programming formulations are proposed, in which routing and handling decisions are simultaneously optimized, but the handling decisions are restricted to three simplified policies. The formulations are strengthened by means of problem specific valid inequalities. The proposed methods have been extensively tested on instances involving up to 25 customers and hundreds of items. Our results show the impact of the handling aspect on the customer sequencing and indicate that the simplified handling policies favorably compare with the optimal one. [ABSTRACT FROM AUTHOR]

This paper discusses the integrated vehicle- and crew-scheduling problem in public transit with multiple depots. It is well known that the integration of both planning steps discloses additional flexibility that can lead to gains in efficiency, compared to sequential planning. We present a new modeling approach that is based on a time-space network representation of the underlying vehicle-scheduling problem. The integrated problem is solved with column generation in combination with Lagrangian relaxation. The column generation subproblem is modeled as a resource-constrained shortest-path problem based on a novel time-space network formulation. Feasible solutions are generated by a heuristic branch-and-price method that involves fixing service trips to depots. Numerical results show that our approach outperforms other methods from the literature for well-known test problems. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of minimizing the staffing cost of a same-day courier company subject to service-level requirements. The problem has been modeled as an integer program with nonlinear probabilistic constraints. We have devised a heuristic procedure to explore the search space efficiently through an approximated neighborhood evaluation (ANE) model, relying on the estimation (via simulation) of a reduced number of parameters. Computational results show that, compared to traditional neighborhood search procedures, the ANE approach provides significant cost reductions in a typical same-day courier setting. [ABSTRACT FROM AUTHOR]

Scheduling problems arise in many applications in process industries. However, despite various efforts to develop efficient scheduling methods, current approaches cannot be used to solve instances of industrial importance in reasonable time frames. The goal of this paper is the development of a dynamic decomposition framework that exploits the structure of the problem and is well suited for grid computing. The problem we study is the simultaneous batching and scheduling of multistage batch processes for which the binary decision variables are batch selection, batch-unit assignment, and batch sequencing on units. We present methods to decompose the original problem into a number of subproblems in a dynamic fashion. First, we discuss the generation of subproblems based on fixing the batch-selection variables. Second, we generate subproblems by fixing the batch-unit assignment variables in a bottlenecking stage. Third, we generate subproblems by fixing the last batch in the sequence on each unit of the bottlenecking stage. Furthermore, the second and third methods can be carried out in various combinations. Alternatively, a problem can be decomposed into a number of promising subproblems using an automatic strong branching scheme. Our results show that the proposed method can be used on a grid computer to solve large problems to optimality in a reasonable computational time. [ABSTRACT FROM AUTHOR]

Production planning on multiple parallel machines is an interesting problem, both from a theoretical and practical point of view. The parallel machine lot-sizing problem consists of finding the optimal timing and level of production and the best allocation of products to machines. In this paper, we look at how to incorporate parallel machines in a mixed-integer programming model when using commercial optimization software. More specifically, we look at the issue of symmetry. When multiple identical machines are available, many alternative optimal solutions can be created by renumbering the machines. These alternative solutions lead to difficulties in the branch-and-bound algorithm. We propose new constraints to break this symmetry. We tested our approach on the parallel machine lot-sizing problem with setup costs and times, using a network reformulation for this problem. Computational tests indicate that several of the proposed symmetry-breaking constraints substantially improve the solution time, except when used for solving the very easy problems. The results highlight the importance of creative modeling in solving mixed-integer programming problems-specifically, the potential added value of symmetry-breaking constraints. [ABSTRACT FROM AUTHOR]

Assembly line balancing problems are concerned with the optimization of manufacturing processes. In this paper we consider the so-called simple assembly line balancing problem with the objective of minimizing the number of used workstations. This problem is denoted by SALB-1 in the literature. For tackling this problem, we present a so-called Beam-ACO approach. This technique results from hybridizing the metaheuristic ant colony optimization with beam search. The experimental results show that our algorithm is a state-of-the-art method for this problem. It can solve 263 of 269 existing benchmark instances to optimality. [ABSTRACT FROM AUTHOR]

This paper introduces the first exact approach for constructing aircrew member personalized monthly work schedules when a preferential bidding system (PBS) is used. With such a system, each employee bids for his/her preferred activities, yielding a bidding score for each feasible schedule. The PBS problem thus consists of assigning to each employee a schedule that maximizes his/her preferences, in order of seniority, while covering all crew pairings. The proposed exact solution approach relies on column generation, and when a tentative maximum score for a crew member is established, it explicitly enumerates for that employee all feasible schedules with that score. Tests on real-life cases show that this approach can substantially improve the quality of the solutions produced by the best known existing method in similar computational times. [ABSTRACT FROM AUTHOR]

The placement problem is that of packing a set of rectangles into a minimum-area enclosing rectangle. Since it is difficult to optimize directly on a placement, a number of topological representations have been presented in the literature. One of the most successful is the sequence pair representation. As opposed to previous papers using sequence pair, we do not make use of the corresponding constraint graph, but interpret the sequences as a packing order in a constructive algorithm. All placements generated are semi-normalized, i.e., each module is moved as far left and down as possible according to the current packing contour. It is shown that the two interpretations are equivalent for any minimum-area placement, and for a given sequence pair the new interpretation results in a placement using no more area than the constraint graph interpretation. The transformation runs in O(n log log n) time and it is able to handle various constraints on the location of modules. Computational results based on a simulated-annealing framework show that the algorithm is able to improve significantly on the best found solutions for benchmark very large-scale integrated (VLSI) circuit design problems using less than ten seconds of CPU time. For large packing problems it is able to find solutions quickly that waste no more than 3%—5% of the space. [ABSTRACT FROM AUTHOR]

The berth allocation problem is one of the most relevant logistics problems arising in the management of container ports. Depending on assumptions made on the berthing location policy, two classes of the berth allocation problem have been considered in literature: the discrete case and the continuous case. In this paper, the properties of the discrete berth allocation problem, formulated as a dynamic scheduling problem, are analyzed. A new formulation of the problem is proposed, which is shown to be more compact and stronger than another one from the literature; a Lagrangean heuristic algorithm is developed; and computational results are presented. [ABSTRACT FROM AUTHOR]

Increasing interest has recently been shown in analyzing the worst-case behavior of local search algorithms. In particular, the quality of local optima and the time needed to find the local optima by the simplest form of local search has been studied. This paper deals with worst-case performance of local search algorithms for makespan minimization on parallel machines. We analyze the quality of the local optima obtained by iterative improvement over the jump, swap, multi-exchange, and the newly defined push neighborhoods. Finally, for the jump neighborhood we provide bounds on the number of local search steps required to find a local optimum. [ABSTRACT FROM AUTHOR]

This paper considers the multimode resource-constrained project-scheduling problem (MRCPSP) with a minimum-makespan objective. An exact branch and cut algorithm is presented based on the integer linear programming (ILP) formulation of the problem. In the preprocessing stage, lower bounds on the distance between each pair of precedence-constrained activities are derived. These bounds are used to reduce the number of variables in the model and to generate cuts that tighten the linear programming relaxation. The solution process is accelerated by an adaptive branching scheme in conjunction with a bound-tightening scheme that is called iteratively after branching. To find good feasible solutions in the early stages of the computations, a high-level neighborhood search strategy known as local branching is included. Here, a neighborhood of a feasible solution is defined by the linear inequalities in the ILP model and is searched first. As implemented, the full algorithm is exact rather than heuristic in nature. Numerical results are reported for 20- and 30-activity benchmark problems. These are the largest instances available and are generally viewed to be notoriously difficult. Up until now, there were no confirmed optimal solutions for any of the 552 30-activity instances. We were able to find several better solutions and to show that at least 506 are optimal. [ABSTRACT FROM AUTHOR]

Traditional methods model the billion-dollar airline crew scheduling problem as deterministic and do not explicitly include information on potential disruptions. Instead of modeling the crew scheduling problem as deterministic, we consider a stochastic crew scheduling model and devise a solution methodology for integrating disruptions in the evaluation of crew schedules. The goal is to use that information to find robust solutions that better withstand disruptions. Such an approach is important because we can proactively consider the effects of certain scheduling decisions. By identifying more robust schedules, cascading delay effects are minimized. In this paper we describe our stochastic integer programming model for the airline crew scheduling problem and develop a branching algorithm to identify expensive flight connections and find alternative solutions. The branching algorithm uses the structure of the problem to branch simultaneously on multiple variables without invalidating the optimality of the algorithm. We present computational results demonstrating the effectiveness of our branching algorithm. [ABSTRACT FROM AUTHOR]

In the locomotive-scheduling problem (or the locomotive-assignment problem), we must assign a consist (a set of locomotives) to each train in a preplanned train schedule so as to provide each train with sufficient locomotive power to pull the train from its origin to its destination. Locomotive-scheduling problems are among the most important problems in railroad scheduling. In this paper, we report the results of a study on the locomotive-scheduling problem as it is faced by CSX Transportation, a major U.S. railroad company. We consider the planning version of the locomotive-scheduling model (LSM) in which multiple types of locomotives exist, and we need to decide which set of locomotives should be assigned to each train. We present an integrated model that determines: the set of active and deadheaded locomotives for each train; the light-traveling locomotives from power sources to power sinks; and train-to-train connections (for which we specify which inbound trains and outbound trains can directly connect). An important feature of our model is that we explicitly consider consist bustings and consistency. A consist is said to be busted when a set of locomotives coming on an inbound train is broken into subsets to be reassigned to two or more outbound trains. A solution is consistent over a week if a train receives the same locomotive assignment each day that it runs. We will provide a mixed-integer programming (MIP) formulation of the locomotive-assignment problem. However, an MIP of this size cannot be solved to optimality or near optimality in acceptable running times using commercially available software. Using problem decomposition, integer programming, and very large-scale neighborhood search, we have developed a solution technique to solve this problem within 30 minutes of computation time on a Pentium III computer. Our solution obtained a potential savings of over 400 locomotives over the solution obtained by the in-house software developed by CSX. [ABSTRACT FROM AUTHOR]

This paper presents two different models and algorithms for integrated vehicle and crew scheduling in the multiple-depot case. The algorithms are both based on a combination of column generation and Lagrangian relaxation. Furthermore, we compare those integrated approaches with each other and with the traditional sequential one on randomly generated, as well as real-world, data instances for a suburban/extraurban mass transit system. To simulate such a transit system, we propose a new way of randomly generating data instances such that their properties are the same as for our real-world instances. [ABSTRACT FROM AUTHOR]

Train units need regular preventive maintenance. Given the train units that require maintenance in the forthcoming one to three days, the rolling stock schedule must be adjusted so that these urgent units reach the maintenance facility in time. Maróti and Kroon (2004) propose a model that requires a large amount of input data. In this paper we describe a less involved multicommodity flow type model for this maintenance routing problem. We study the complexity of the problem. It turns out that the feasibility problem for a single urgent train unit is polynomially solvable but the optimization version is NP-hard. Finally, we report our computational experiments on practical instances of NS Reizigers, the main Dutch operator of passenger trains. [ABSTRACT FROM AUTHOR]

We propose local search algorithms for the vehicle routing problem with soft time-window constraints. The time-window constraint for each customer is treated as a penalty function, which is very general in the sense that it can be nonconvex and discontinuous as long as it is piecewise linear. In our algorithm, we use local search to assign customers to vehicles and to find orders of customers for vehicles to visit. Our algorithm employs an advanced neighborhood, called the cyclic-exchange neighborhood,in addition to standard neighborhoods for the vehicle routing problem. After fixing the order of customers for a vehicle to visit, we must determine the optimal start times of processing at customers so that the total penalty is minimized. We show that this problem can be efficiently solved by using dynamic programming, which is then incorporated in our algorithm. We report computational results for various benchmark instances of the vehicle routing problem. The generality of time-window constraints allows us to handle a wide variety of scheduling problems. As an example, we mention in this paper an application to a production scheduling problem with inventory cost, and report computational results for real-world instances. [ABSTRACT FROM AUTHOR]