Search

This article presents a mixed-integer linear-programming formulation for integrating short-term maintenance planning in a network-wide railway rolling stock circulation problem. This is a key problem in railway rostering planning that requires covering a given set of services and maintenance works with a minimum amount of rolling stock units. In our formulation, a rostering solution is viewed as a minimal cost Hamiltonian cycle in a graph with service pairings, empty runs, and short-term maintenance tasks. We use a commercial MILP solver to compute efficient solutions in a short time. Experimental results on real-world scenarios from the main Italian railway company Trenitalia show that this integrated approach can reduce significantly the number of trains and empty runs when compared with the current rolling stock circulation plan.

We consider the job shop scheduling problem with tvm jobs. We consider a broad class of non-regular, quasi-convex functions of the completion time of the two jobs. We show that the optimal solution, for this class of objective functions, can be computed in O(rlogr + logH) time, where r is the number of operation pairs using the same machine, and H is the maximum operation processing time. This paper deals with the job shop problem when two jobs have to be performed in the shop. The most efficient solution algorithm for this problem is Brucker's algorithm (4), which addresses the case in which the objective is the minimization of the makespan. Sotskov (7) has given a polynomial algorithm for the more general case in which one wants to minimize an arbitrary regular (i.e., nondecreasing) objective function in the completion times of the two jobs. In this paper we extend this analysis to include quasi-convex, nonregular objective functions. Unlike classical results on the job shop with two jobs, the optimal schedule may not be semi-active. Both the sum and the maximum of these two objective functions are considered as performance criteria. Our approach consists in first finding a set of nondominated solutions, i.e., schedules which are Paretooptimal from the viewpoint of the two jobs, and then searching for an overall optimum among these solutions. Both steps are carried out in polynomial time, as long as all processing times are integers.

Given a graph G=(V,E) , HCN(L(G)) is the minimum number of edges to be added to its line graph L(G) to make L(G) Hamiltonian. This problem is known to be NP-hard for general graphs, whereas an O (|V| 5 ) algorithm exists when G is a tree. In this paper a linear algorithm for finding HCN(L(G)) when G is a tree is proposed.

In the production of perishable goods, particular stress is often given to performance indicators generally less critical in such manufacturing settings as metal-cutting, or mechanical/electronic assembly. For instance, in food or biochemical productions, a prominent interest of the producer is to reduce the time from distribution to the so-called best-before end. A scheduling problem with a goal of this sort is here addressed. The decision variables considered are launching and completion times of parts in a production line with critical aspects in the initial and/or final stages. The basic problem is to find an assignment of a maximum number of products to launching and completion times, so that no two products are assigned the same launching or completion time: feasible solutions have therefore the form of three-dimensional matchings. The problem is studied under two independent respects, assuming either (i) the relative perishability of products or (ii) the feasibility of launching/completion time pairs not affected by the intermediate transformation stage. We show that the problem is NP-Complete, even under such a ranking assumption as (i), whereas is in P under assumption (ii). Polynomial-time algorithms are also proposed to solve other optimization versions of the problem (in two cases, based on the identification of a matroid structure).

This paper deals with an operational problem faced by railway traffic controllers. During daily operations, trains need to be scheduled on a bidirectional single-track line with multiple stations to cope with various sources of disturbance that alter the existing timetable. We propose a decision support tool based on a detailed mathematical formulation of the single-line train scheduling problem. State-of-the-art scheduling and rerouting optimization algorithms are adopted to compute good quality solutions in a short computation time. Practical data from RFI, train delays and disrupted tracks are investigated in order to quantify the gap, in terms of delay minimization, between the solutions provided by optimization and by the current FIFO-based dispatching practice. The computational results show that advanced scheduling algorithms are useful when dealing with any kind of disturbed traffic situation, since train ordering decisions have to be taken at each station in both traffic directions. Differently, advanced rerouting algorithms are more suitable when mixed traffic is scheduled, since overtaking between trains travelling in the same direction is only favourable when trains travel at different speeds.

This paper deals with the problem of part input sequencing in an automated flow shop system. The system consists of one input/output station, two machines and one AGV, which is used for all part transfer operations throughout the cell. The objective is the minimization of the makespan. This cell architecture has recently received considerable attention in the literature. Here we consider the case in which the two machines are equipped by a swapping device, allowing the AGV to exchange a new part for the one released by the machine. A similar device exists for the input/output station. If the transportation times are small enough, the problem can be formulated as a two-machine flow shop with limited intermediate buffer, which is NP-hard. Here we analyze the problem in the context of lot processing, i.e., when identical parts must be processed consecutively. Each set of identical parts forms a lot. The number of parts in the lot is the size of the lot. If the size of the ith lot is larger than a value b*i, ...

This paper addresses the real-time problem of scheduling aircraft in a Terminal Control Area (TCA). At a congested airport, airborne decisions need to be taken regarding take-off and landing operations in given time horizons of traffic prediction. In this work, aircraft are rescheduled at holding circles, air segments and runways during disturbances in order to minimize the propagation of aircraft delays. We formulate this problem via an alternative graph formulation, i.e., a detailed job shop scheduling model of the aircraft scheduling problem. A rolling horizon framework is introduced to manage busy traffic situations with a large number of delayed aircraft. As scheduling algorithms, we compare a Branch and Bound (BB) algorithm with a First Come First Served (FCFS) rule that we use as a surrogate for the dispatchers behaviour. The solution algorithms are evaluated on practical size instances from Roma Fiumicino and Milano Malpensa airports, in Italy. Traffic disturbances are simulated for the assessment of the solution procedures. We distinguish between entrance aircraft delays and small random variations on the aircraft entry times in the TCA. Rolling horizon parameters are evaluated such as the extension of the current traffic flow forecast and the time shift between the start of successive traffic predictions. Experimental results demonstrate that BB solutions are of better quality compared to FCFS solutions. BB computes feasible schedules that better minimizes aircraft delay and travel time minimization. Also, BB requires less frequent changes of aircraft scheduling decisions between consecutive traffic predictions. The performance of BB is less affected by random variations of entry times.

Railway conflict detection and resolution is the daily task faced by dispatchers and consists of adjusting train schedules whenever disturbances make the timetable infeasible. The main objective pursued by dispatchers in this task is the minimization of train delays, while train operating companies are also interested in other indicators of passenger dissatisfaction. The two objectives are conflicting whenever train delay reduction requires cancellation of some connected services, causing extra waiting times to transferring passengers. In fact, the infrastructure company and the train operating companies discuss on which connection to keep or drop in order to reach a compromise solution. This paper considers the bi-objective problem of minimizing train delays and missed connections in order to provide a set of feasible non-dominated schedules to support this decisional process. We use a detailed alternative graph model to ensure schedule feasibility and develop two heuristic algorithms to compute the Pareto front of non-dominated schedules. Our computational study, based on a complex and densely occupied Dutch railway network, shows that good coordination of connected train services is important to achieve real-time efficiency of railway services since the management of connections may heavily affect train punctuality. The two algorithms approximate accurately the Pareto front in a limited computation time.

This paper studies quantitative methods for evaluating the potential benefits of introducing new advanced tracking technologies in the pharmaceutical industry with special reference to radio frequency identification (RFID). RFID technology is an effective way for increasing the quality of the data that are used to generate production schedules, but there is a lack of scientific research to quantify the return on investment that can be achieved in practice. In this work, we distinguish two major sources of data unreliability: one is the inherent stochasticity of operations, which cannot be reduced by RFID, and the other one is the data estimation error, which can be significantly reduced by RFID. We focus on the marginal contribution of the latter quantity to the productivity of the packaging department of a pharmaceutical plant, propose a systematic method for assessing this impact and discuss its implementation in a practical test case. Our results confirm that advanced tracking technologies in combination with effective scheduling procedures show a significant potential for improving productivity. Extensions to other production environments and their issues associated with scheduling problems are also discussed.

During real-time traffic management, the railway system suffers perturbations. The task of dispatchers is to monitor traffic flow and to compute feasible rescheduling solutions in case of perturbed operations. The main objective of the infrastructure manager is delay minimization, but the dispatchers also need to comply with the objectives of the train operating companies. This paper presents an innovative optimization framework in order to reschedule trains with different classes of priority, that can be computed statically or dynamically in order to include the needs of different stakeholders. An iterative train scheduling procedure is proposed in order to compute feasible train schedules for an ordered set of priority classes, from the highest one to the lowest one. At each step, the procedure focuses on the current priority class, preserving solution quality from the higher priority classes and neglecting lower priority classes in the optimization of train orders and times. The multi-class rescheduling problem is formulated via alternative graphs that are able to model precisely train movements at the microscopic level of block sections and block signals. Each step of the iterative train scheduling procedure is solved to optimality by a state-of-the-art branch and bound algorithm. The results show an interesting gap between single-class and multi-class rescheduling problems in terms of delay minimization. Each priority class is also evaluated in order to assess the performance of the different rescheduling solutions.

Train services are planned in detail, defining several months in advance the train order and timing at crossings, junctions and platform tracks. A robust timetable is able to deal with minor perturbations even though in case of large delays or blocking of some tracks multiple timetable modifications are required in order to recover the feasibility of operations. Due to the interaction between trains, such exceptional situations result in consecutive delays to other trains in the network, making the railway system very vulnerable to disruptions. This paper investigates disruption handling strategies for large and busy railway networks. We consider seriously disturbed traffic conditions on double track railway lines where some block sections of one track are unavailable for traffic, e.g., due to a temporary track blockage, and disrupted train services are rerouted in other areas while still with the same origin and destination. Centralized approaches are used to solve the whole scheduling problem. Distributed approaches are also presented to manage effectively larger networks, in which a coordinator sets ad-hoc constraints between areas and delegates the scheduling decisions to local schedulers. Computational experiments on a large Dutch railway network, actually controlled by ten dispatchers, assess the performance of the centralized and distributed procedures, showing that both the procedures face increasing difficulty in finding feasible schedules in a short computation time for increasing time horizons of traffic prediction.

Railway dispatchers reschedule trains in real-time in order to limit the propagation of disturbances and to regulate traffic in their respective dispatching areas by minimizing the deviation from the off-line timetable. However, the decisions taken in one area may influence the quality and even the feasibility of train schedules in the other areas. Regional control centers coordinate the dispatchers' work for multiple areas in order to regulate traffic at the global level and to avoid situations of global infeasibility. Differently from the dispatcher problem, the coordination activity of regional control centers is still underinvestigated, even if this activity is a key factor for effective traffic management. This paper studies the problem of coordinating several dispatchers with the objective of driving their behavior towards globally optimal solutions. With our model, a coordinator may impose constraints at the border of each dispatching area. Each dispatcher must then schedule trains in its area by producing a locally feasible solution compliant with the border constraints imposed by the coordinator. The problem faced by the coordinator is therefore a bilevel programming problem in which the variables controlled by the coordinator are the border constraints. We demonstrate that the coordinator problem can be solved to optimality with a branch and bound procedure. The coordination algorithm has been tested on a large real railway network in the Netherlands with busy traffic conditions. Our experimental results show that a proven optimal solution is frequently found for various network divisions within computation times compatible with real-time operations.

This study compares approximation techniques for the estimation of the operational availability of a corrective maintenance system. The assessment is based on the practical maintenance of safety equipments in operation in 38 Italian Airports. A single echelon one-for-one ordering policy with complete pooling is analyzed, with a deterministic rule for lateral transshipments. With this policy, the state probabilities of the associated Markov model cannot be expressed in product form. Since the exact computation of the state probabilities is not practical as the number of states in the Markov chain increases, this study describes three approximation techniques and assesses their performance in terms of computational effort, memory requirement and error with respect to the exact value. The first two techniques are based on a method by Alfredsson and Verrijdt and on the Equivalent Random Traffic method, respectively. The idea of both methods is to approximate the state probabilities with a product form, so that the Markov chain can be decomposed. The third technique is based on the multi-dimensional scaling down approach, which studies an equivalent reduced Markov chain rather than decomposing the original one.

"This paper addresses quantitative methods. for estimating the value of information from ITS in. urban freight distribution. A real-life application on. the retail distribution of perishable goods is considered.. The problem is formulated as a vehicle routing problem. with soft time windows and time-dependent travel. times, and solved by using information affected by. different degrees of detail and reliability. The practical. performance of these solutions is then evaluated by. simulation, to assess the joint benefit of using more reliable. and detailed information with different solution. algorithms."

This study addresses the real-time problem of aircraft conflict detection and resolution in a terminal manoeuvring area (TMA). The problem is to take conflict-free airborne decisions on take-off and landing operations at a congested airport. Aircraft control actions at air segments and runways include timing, sequencing, holding and routing. Rescheduling and rerouting decisions aim at balancing the runway workload while minimising delay propagation. This problem can be viewed as a job shop scheduling problem with additional real-world constraints. Two formulations are analysed in which air segments, runways and holdings are modelled explicitly. In the first formulation the entrance time of each aircraft in the TMA is fixed, in the second it can be defined by the procedure. A truncated branch and bound algorithm computes aircraft schedules with fixed routes. The branch and bound is then incorporated in a tabu search scheme for aircraft rerouting. The solution approach is tested on the Rome Fiumicino airport, the main Italian airport, under congested traffic conditions and for several aircraft delay configurations. Computational results show a significant delay reduction when real-time rerouting is allowed in combination with rescheduling with respect to real-time rescheduling with fixed routes. The improvement is larger for the second formulation. © 2012 The Institution of Engineering and Technology.

The pharmaceutical marketplace is dominated by large multinational companies, competing worldwide, with a global presence in branded products. Retaining marketshare requires standards of product quality and reliability close to 100%, attained at sustainable cost. Wholesalers and final customers expect reliability and quality from pharmaceutical companies, which face an increasing challenge to achieve such standards. Reliable production plans are critical to this aim. In fact, to achieve 100% availability of final products, it is not sufficient to attain excellence in each phase of the planning process from strategic planning to real-time scheduling, but it is also important to effectively manage the coordination between these different phases.

This chapter is the first thorough assessment of a full implementation of the concept of dynamic traffic management in combination with advanced optimization tools. In the last years, several studies on partial implementations of this concept have been carried out reporting promising results. The development of new strategies for railway traffic control experienced an increasing interest due to the expected growth of traffic demand and to the limited possibilities of enhancing the infrastructure, which increase the needs for efficient use of resources and the pressure on traffic controllers. Improving the efficiency requires advanced decision support tools that accurately monitor the current train positions and dynamics, and other operating conditions, predict the potential conflicts and reschedule trains in real-time such that consecutive delays are minimized. We carry on our study using an innovative computerized railway traffic management system, called ROMA (Railway traffic Optimization by Means of Alternative graphs). An extensive computational study is carried out, based on two complex and busy dispatching areas of the Dutch rail network. We study practical size instances and different types of disturbances, including train delays and blocked tracks. Our results show the high potential of ROMA as a support tool to improve punctuality through intelligent use of the rail infrastructure and efficient use of the available transport capacity.

This paper addresses the problem of train conflict detection and resolution, which is dealt every day by traffic controllers to adapt the timetable to delays and other unpredictable events occurring in real-time. We describe a number of algorithmic improvements implemented in the real-time traffic management system ROMA (Railway traffic Optimization by Means of Alternative graphs), achieved by incorporating effective rescheduling algorithms and local rerouting strategies in a tabu search scheme. We alternate a fast heuristic and a truncated branch and bound algorithm for computing train schedules within a short computation time, and investigate the effectiveness of using different neighborhood structures for train rerouting. The computational experiments are based on practical size instances from a dispatching area of the Dutch railway network and include complex disturbances with multiple late trains and blocked tracks. Several small instances are solved to optimality in order to compare the heuristic solutions with the optimum. For small instances, the new tabu search algorithms find optimal solutions. For large instances, the solutions generated by the new algorithms after 20 s of computation are up to more than 15% better than those achieved within 180 s by the previous version of ROMA.

This paper studies the problem of sequencing aircraft take-off and landing operations at congested airports. We introduce and analyze alternative detailed formulations and solution algorithms for scheduling arrival and departure times of the aircrafts, such that the delay with respect to the scheduled times is minimized. The aircraft scheduling problem (ASP) is viewed as an extension of the job shop scheduling problem with additional real-world constraints and formulated by using alternative graphs. Two alternative formulations model the required time separation among aircrafts in air segments and runways according to safety regulations and differ for the level of detail used to represent the holding circles. Scheduling rules, heuristic and exact methods are implemented and tested on practical size instances of the Fiumicino airport, the busiest airport in Italy. We show that two versions of an innovative branch and bound algorithm are always able to find good solutions in a few seconds and often improve the best solution computed by the scheduling heuristics. Optimality is proved in less than two minutes for more than half of the instances.

This paper addresses a practical scheduling problem arising in the packaging department of a pharmaceutical industrial plant. The problem is modeled as a multi-purpose machine scheduling problem with setup and removal times, release and due dates and additional constraints related to the scarce availability of tools and human operators. The objective functions are minimization of makespan and maximum tardiness in lexicographic order. Representing a solution with a directed graph allows us to devise an effective tabu search algorithm to solve the problem. Computational experiments, carried on real and randomly generated instances, show the effectiveness of this approach.

In this paper, we develop branch-and-bound algorithms for several hard, two-agent scheduling problems, i.e., problems in which each agent has an objective function which depends on the completion times of its jobs only. Our bounding approach is based on the fact that, for all problems considered, the Lagrangian dual gives a good bound and can be solved exactly in strongly polynomial time. The problems addressed here consist in minimizing the total weighted completion time of the jobs of agent A, subject to a bound on the cost function of agent B, which may be: (i) total weighted completion time, (ii) maximum lateness, (iii) maximum completion time. An extensive computational experience shows the effectiveness of the approach.

In this paper we report on the results of a research project on train traffic control systems, supported by the European Commission. The results of the project include the development of new optimisation models and algorithms for traffic management, and a general architecture for train traffic control, capable of managing both fixed block and moving block signaling safety concepts. This paper focuses in particular on models and algorithms for real time conflict resolution. Computational results are reported, based on a portion of the Dutch railway network, on the high-speed line Paris-Brussels-Amsterdam.

A standard practice to improve punctuality of railway services is the addition of time reserves in the timetable to recover perturbations occurring in operations. However, time reserves reduce line capacity, and the amount of time reserves that can be inserted in congested areas is, therefore, limited. In this paper, we investigate the new concept of flexible timetable as an effective policy to improve punctuality without decreasing the capacity usage of the lines. The principle of a flexible timetable is to plan less in the timetable and to solve more inter-train conflicts during operations. The larger degree of freedom left to real-time management offers better chance to recover disturbances. We illustrate a detailed model for conflict resolution, based on the alternative graph formulation, and analyze different algorithms for resolving conflicts, based on simple local rules or global optimization. We compare the solutions obtained for different levels of flexibility and buffer time inserted in the timetable. An extensive computational study, based on a bottleneck area of the Dutch railway network, confirms that flexibility is a promising concept to improve train punctuality and to increase the throughput of a railway network.

Traffic controllers regulate railway traffic by sequencing train movements and setting routes with the aim of ensuring smooth train behaviour and limiting, as much as possible, train delays. In this paper, we describe the implementation of a real-time traffic management system, called ROMA (Railway traffic Optimization by Means of Alternative graphs), to support controllers in the everyday task of managing disturbances. We make use of a branch-and-bound algorithm for sequencing train movements, while a local search algorithm is developed for rerouting optimization purposes. The compound problem of routing and sequencing trains is approached iteratively, computing an optimal train sequencing for given train routes and then improving this solution by locally rerouting some trains. An extensive computational study is carried out, based on a dispatching area of the Dutch railway network. We study practical size instances, and include in the model important operational constraints, including rolling stock and passenger connections. Different types of disturbances are analysed, including train delays and blocked tracks. Comparison with common dispatching practice shows the high potential of the system as an effective support tool to improve punctuality.

In order to face the expected growth of transport demand in the next years, several new traffic control policies have been proposed and analyzed both to generate timetables and to effectively manage the traffic in real-time. In this paper, a detailed optimization model is used to analyze one such policy, called green wave, which consists in letting trains wait at the stations to avoid speed profile modifications in open corridors. Such policy is expected to be especially effective when the corridors are the bottleneck of the network. However, there is a lack of quantitative studies on the real-time effects of using this policy. To this end, this work shows a comparison of the delays obtained when trains are allowed or not to change their speed profile in open corridors. An extensive computational study is described for two practical dispatching areas of the Dutch railway network.

This paper addresses a scheduling problem arising in the real time management of a metro rail terminus. It mainly consists in routing incoming trains through the station and scheduling their departures with the objective of optimizing punctuality and regularity of train service. The purpose of this work is to develop an automated train traffic control system, able to directly implement most traffic control actions, without the authorization of the local area manager. The scheduling problem is modeled as a bicriteria job shop scheduling problem with additional constraints. The two objective functions, in lexicographical order, are the minimization of tardiness/earliness and the headway optimization. The problem is solved in two steps. At first a heuristic builds a feasible solution by considering the first objective function. Then the regularity is optimized without deteriorating the first objective function. Computational results show that the system is able to manage the terminus very efficiently.

Scheduling models deal with the best way of carrying out a set of jobs on given processing resources. Typically, the jobs belong to a single decision maker, who wants to find the most profitable way of organizing and exploiting available resources, and a single objective function is specified. If different objectives are present, there can be multiple objective functions, but still the models refer to a centralized framework, in which a single decision maker, given data on the jobs and the system, computes the best schedule for the whole system. This approach does not apply to those situations in which the allocation process involves different subjects (agents), each having his/her own set of jobs, and there is no central authority who can solve possible conflicts in resource usage over time. In this case, the role of the model must be partially redefined, since rather than computing "optimal" solutions, the model is asked to provide useful elements for the negotiation process, which eventually leads to a stable and acceptable resource allocation. Multi-agent scheduling models are dealt with by several distinct disciplines (besides optimization, we mention game theory, artificial intelligence etc), possibly indicated by different terms. We are not going to review the whole scope in detail, but rather we will concentrate on combinatorial models, and how they can be employed for the purpose on hand. We will consider two major mechanisms for generating schedules, auctions and bargaining models, corresponding to different information exchange scenarios.

We consider the scheduling problems arising when several agents, each owning a set of nonpreemptive jobs, compete to perform their respective jobs on one shared processing resource. Each agent wants to minimize a certain cost function, which depends on the completion times of its jobs only. The cost functions we consider in this paper are maximum of regular functions (associated with each job), number of late jobs and total weighted completion time. The different combinations of the cost functions of each agent lead to various problems, whose computational complexity is analysed in this paper. In particular, we investigate the problem of finding schedules whose cost for each agent does not exceed a given bound for each agent.

The paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits.

In this paper we deal with solution algorithms for a general formulation of the job shop problem, called alternative graph. We study in particular the job shop scheduling problem with blocking and/or no-wait constraints. Most of the key properties developed for solving the job shop problem with infinite capacity buffer do not hold in the more general alternative graph model. In this paper we report on an extensive study on the applicability of a metaheuristic approach, called rollout or pilot method. Its basic idea is a look-ahead strategy, guided by one or more subheuristics, called pilot heuristics. Our results indicate that this method is competitive and very promising for solving complex scheduling problems.

We consider the scheduling problems arising when two agents, each with a set of nonpreemptive jobs, compete to perform their respective jobs on a common processing resource. Each agent wants to minimize a certain objective function, which depends on the completion times of its jobs only. The objective functions we consider in this paper are maximum of regular functions (associated with each job), number of late jobs, and total weighted completion times. We obtain different scenarios, depending on the objective function of each agent, and on the structure of the processing system (single machine or shop). For each scenario, we address the complexity of various problems, namely, finding the optimal solution for one agent with a constraint on the other agent's cost function, finding single nondominated schedules (i.e., such that a better schedule for one of the two agents necessarily results in a worse schedule for the other agent), and generating all nondominated schedules.

In this paper we introduce a new class of greedy heuristics for general job shop scheduling problems. In particular we deal with the classical job shop, i.e. with unlimited capacity buffer, and job shop problems with blocking and no-wait. The proposed algorithm family is a simple randomized greedy family based on a general formulation of the job shop problem. We report on an extensive study of the proposed algorithms, and comparisons with other greedy algorithms are presented.

The adaptation of the academic job shop scheduling model to industrial practice is well known to be rich of difficulties owing to the gap between scheduling theory and practice. On the other hand, several authors observed that the disjunctive graph formulation of Roy and Sussman was more robust than the job shop model itself. In fact, the disjunctive graph can be easily adapted to deal with many practical issues. This paper moves a step closer in the direction of generalizing the existing mathematical models in order to capture relevant aspects of complex factory scheduling problems. It considers an extension of the disjunctive graph, called an alternative graph, and allows it to be modelled in a precise way to solve effectively a number of complex practical scheduling problems for which there were no successful methodologies. Several examples are presented and a complex industrial application arising in the production of steel is provided. Finally, the performance of a new fast heuristic both on real dat...

In this paper, we consider the problem of assigning operations to an ordered sequence of non-identical workstations, observing precedence relationships and cycle time restrictions. The objective is to minimize the cost of the workstations. We first present a dynamic programming algorithm, and introduce several fathoming rules in order to reduce the number of states in the dynamic program. A characterization of a wide class of polynomially solvable instances is given, and computational results are reported.

The minimum storage-time sequencing problem generalizes many well-known problems in combinatorial optimization, such as the directed linear arrangement and the problem of minimizing the weighted sum of completion times, subject to precedence constraints on a single processor. In this paper we propose a new lower bound, based on a Lagrangian relaxation, which can be computed very efficiently. To improve upon this lower bound, we employ a bundle optimization algorithm. We also show that the best bound obtainable by this approach equals the one obtainable from the linear relaxation computed on a formulation whose first Chvatal closure equals the convex hull of all the integer solutions of the problem. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 313–331, 2001

A no-wait robotic cell is an automated flow shop in which a robot is used to move the parts from a machine to the next. Parts are not allowed to wait. We analyze the complexity of the part sequencing problem in a robotic cell with three machines, for different periodical patterns of robot moves, when the objective is productivity maximization.

The material flow management of flexible assembly systems requires to assign a set of operations to a set of machines, and to connect machines by a transportation network, such that a number of constraints is satisfied and some efficiency index is optimized Aim of the paper is to give a general framework to formulate and model, in a formal way, different subproblems arising from embedding an assembly process on different configurations of a flexible production system. We analyze several wide used architectures and material flow policies, and point out some useful properties to design decision rules and evaluate the corresponding optimality bounds. The paper also investigates the computational complexity of various subcases of the problem.

In its basic form the management control of a flexible production system requires to assign a set of operations to a set of machines, and to connect machines by a transportation network, such that a number of constraints is satisfied and some efficiency index is optimized. The aim of the work is to give a general framework to formulate and model, in a formal way, different subproblems arising from embedding an assembly process on different configurations of a flexible production system. Because of the complexity of the overall problem, it is useful to have simple and well structured layouts and procedures that help the design and operation of flexible systems. These layouts and procedures induce additional constraints, due to the products' and the process' features. The paper also investigates the complexity of various subcases of the problem.

This paper deals with the problem of makespan minimization in a flow shop with two machines when the input buffer of the second machine can only host a limited number c of parts. This problem has been shown to be NP-hard for any c > 0 and c < n-1, where n is the number of jobs, by Papadimitriou and Kanellakis (1980). Here we analyze the problem in the context of batch processing, i.e., when identical parts must be processed consecutively. Each set of identical parts forms a batch. The number of parts in the batch is the size of the batch. We first prove that, if the size of the i-th batch is larger than a value b i *, then the makespan minimization problem can be formulated as a special case of TSP and solved in polynomial time. The cost structure of this TSP generalizes the one defined for the two machine no-wait flow shop, i.e., when c=0. However, when the same algorithm is applied to batch sizes smaller than b i * the error goes to zero as the batch sizes approach the values b i *. Hence, we give a closed form expression for b i *.

This paper addresses the real-time problem of aircraft scheduling and routing in terminal control area. A main task of traffic controllers is to mitigate the effects of severe traffic disturbances on the day of operations in the Terminal Control Area (TCA) of an airport. When managing disturbed take-off and landing operations, they need to minimize the delay propagation and, in addition, to reduce the aircraft travel time and energy consumption. The paper tackles the problem of developing effective decision support tools for air traffic monitoring and control in a busy TCA. To this purpose, centralized and rolling horizon traffic control paradigms are implemented and compared. The mathematical formulation is a detailed model of air traffic flows in the TCA based on alternative graphs, that are generalized disjunctive graphs. As for the aircraft scheduling and (re-)routing approaches, the First-In-First-Out (FIFO) rule, used as a surrogate for the behavior of air traffic controllers, is compared with various optimization-based approaches including a branch and bound algorithm for aircraft scheduling with fixed routes, a combined branch and bound and tabu search algorithm for aircraft scheduling and re-routing, and a mixed integer linear programming formulation for simultaneous scheduling and routing. Various hypothetical disturbance scenarios are simulated for a real-world airport case study, Milano Malpensa, and the proposed timing and routing approaches are compared in terms of their performance in the different scenarios. The disturbed traffic situations are generated by simulating multiple delayed arriving/departing aircraft and a temporarily disrupted runway. In general, the optimization approaches are found to improve the solutions significantly compared to FIFO, in terms of aircraft delay minimization. However, there are some trade-offs involved in picking the right approach and paradigms for practical implementations.