A decision support system for the single-depot vehicle rescheduling problem

Disruptions in trips can prevent vehicles from executing their schedules as planned. Mechanical failures, accidents, and traffic congestion often hinder a vehicle schedule. When a vehicle on a scheduled trip breaks down, one or more vehicles need to be rescheduled to serve the passengers/cargo (if there are any) on that trip. The main objective of the vehicle rescheduling problem (VRSP) is to minimize operation and delay costs, while serving the passengers/cargo on the disrupted trip and completing all remaining trips that include the disrupted one. We report on a prototype decision support system (DSS) that recommends solutions for the single-depot rescheduling as well as vehicle scheduling (VSP) problems, since VRSP is closely related to VSP. The system was designed for human schedulers to obtain optimal vehicle assignments and reassignments. An experimental study, using randomly generated data, shows the efficiency of the developed algorithm. A real world problem, which involves the solid waste collection operational planning for a Brazilian city, is selected as the case study to illustrate the effectiveness of the developed DSS.     

SmartGantt – An intelligent system for real time rescheduling based on relational reinforcement learning

With the current trend towards cognitive manufacturing systems to deal with unforeseen events and disturbances that constantly demand real-time repair decisions, learning/reasoning skills and interactive capabilities are important functionalities for rescheduling a shop-floor on the fly taking into account several objectives and goal states. In this work, the automatic generation and update through learning of rescheduling knowledge using simulated transitions of abstract schedule states is proposed. Deictic representations of schedules based on focal points are used to define a repair policy which generates a goal-directed sequence of repair operators to face unplanned events and operational disturbances. An industrial example where rescheduling is needed due to the arrival of a new/rush order, or whenever raw material delay/shortage or machine breakdown events occur are discussed using the SmartGantt prototype for interactive rescheduling in real-time. SmartGantt demonstrates that due date compliance of orders-in-progress, negotiating delivery conditions of new orders and ensuring distributed production control can be dramatically improved by means of relational reinforcement learning and a deictic representation of rescheduling tasks.     

Duty-period-based network model for crew rescheduling in European airlines

Airline rescheduling is a relatively new field in airline Operations Research but increasing amounts of traffic will make disturbances to the original schedule more frequent and more severe. Thus, the need to address the various problems arising from this situation with systematic, cost-efficient approaches is becoming more urgent. One such problem is crew rescheduling where after a disturbance in the crew schedule the aim is to determine new crew assignments that minimize the `impact’ on the original schedule. In this work we present a new duty-period-based formulation for the airline crew rescheduling problem that is tailored to the needs of European airlines. It uses a new type of resource constraints to efficiently cover the various labor regulations. A solution method based on branch-and-price is tested on various rescheduling scenarios, each with several distinct cases. Results show that the solution method is capable of providing solutions within the short period of time available to a rescheduler after a disturbance occurs.     

Rescheduling Manufacturing Systems: A Framework of Strategies, Policies, and Methods

Many manufacturing facilities generate and update production schedules, which are plans that state when certain controllable activities (e.g., processing of jobs by resources) should take place. Production schedules help managers and supervisors coordinate activities to increase productivity and reduce operating costs. Because a manufacturing system is dynamic and unexpected events occur, rescheduling is necessary to update a production schedule when the state of the manufacturing system makes it infeasible. Rescheduling updates an existing production schedule in response to disruptions or other changes. Though many studies discuss rescheduling, there are no standard definitions or classification of the strategies, policies, and methods presented in the rescheduling literature. This paper presents definitions appropriate for most applications of rescheduling manufacturing systems and describes a framework for understanding rescheduling strategies, policies, and methods. This framework is based on a wide variety of experimental and practical approaches that have been described in the rescheduling literature. The paper also discusses studies that show how rescheduling affects the performance of a manufacturing system, and it concludes with a discussion of how understanding rescheduling can bring closer some aspects of scheduling theory and practice.     

分布式整数规划及其在航线扰动问题的应用

在航空公司的运作中时常会出现干扰它正常运作的现象。在这种情况下,航空公司必须马上制定航线修复计划使受到干扰的航线尽快复原,以防止更大面积的航班取消和航班延误。提出一种基于递增映射迭代方法的分布式整数规划算法来解决由于机场关闭引起的航线扰动问题。整个问题分成了两个子问题：可行航线的生成和飞机的重指派。第一个子问题的问题空间被初始点分割方法分割成了若干片段。然后在一个分布式的计算网络中使用递增映射迭代方法在分得的每个片段上同时求解第一个子问题。得到的可行航线用来求解第二个子问题。最后的算例结果可以发现提出的方法要好于CPLEX和多目标基因算法。     

多次扰动下单机双目标的滚动部分重调度

This paper discusses the single-machine rescheduling problem with efficiency and stability as criteria, where more than one disruption arises in large-scale dynamic circumstances. Partial rescheduling (PR) strategy is adopted after each disruption and a rolling mechanism is driven by events in response to disruptions. Two kinds of objective functions are designed respectively for PR sub-problem involving in the interim and the terminal of unfinished jobs. The analytical result demonstrates that each local objective is consistent with the global one. Extensive computational experiment was performed and the computational results show that the rolling PR strategy with dual objectives can greatly improve schedule stability with little sacrifice in efficiency and provide a reasonable trade-off between solution quality and computational efforts.     

Improving schedule stability in single-machine rescheduling for new operation insertion

The problem studied here entails inserting a new operation into an existing predictive schedule (preschedule) on a (non-preemptive) single machine by rescheduling its operations, so that the resultant schedule is the most stable one among schedules with minimal maximum tardiness. Stability is measured by the sum of absolute deviations of post-rescheduling start times from the pre-rescheduling start times. In addition to several simple heuristics, this study investigates a hybrid branch-and-bound/local-search algorithm. A large set of instances that include cases with inserted idle times allows for tests of the performance of the heuristics for preschedules with varying degrees of robustness. The results show that algorithms can be developed that significantly improve the stability of schedules with no degradation in T_max. In addition, new insights emerge into the robustness characteristics of a preschedule. Specifically, the number of gaps in the schedule, equal distribution of total slack among these gaps, and the slack introduced beyond the amount enforced by release times all have effects on schedule robustness and stability.     

多次打扰下单机双目标的滚动部分重调度

This paper discusses the single-machine rescheduling problem with efficiency and stability as criteria, where more than one disruption arises in large-scale dynamic circumstances. Partial rescheduling (PR) strategy is adopted after each disruption and a rolling mechanism is driven by events in response to disruptions. Two kinds of objective functions are designed respectively for PR sub-problem involving in the interim and the terminal of unfinished jobs. The analytical result demonstrates that each local objective is consistent with the global one. Extensive computational experiment was performed and the computational results show that the rolling PR strategy with dual objectives can greatly improve schedule stability with little sacrifice in efficiency and provide a reasonable trade-off between solution quality and computational efforts.     

Rolling Partial Rescheduling with Dual Objectives for Single Machine Subject to Disruptions

This paper discusses the single-machine rescheduling problem with efficiency and stability as criteria, where more than one disruption arises in large-scale dynamic circumstances. Partial rescheduling (PR) strategy is adopted after each disruption and a rolling mechanism is driven by events in response to disruptions. Two kinds of objective functions are designed respectively for PR sub-problem involving in the interim and the terminal of unfinished jobs. The analytical result demonstrates that each local objective is consistent with the global one. Extensive computational experiment was performed and the computational results show that the rolling PR strategy with dual objectives can greatly improve schedule stability with little sacrifice in efficiency and provide a reasonable trade-off between solution quality and computational efforts.     

The rescheduling arc routing problem

In this paper, the rescheduling arc routing problem is introduced. This is a dynamic routing and scheduling problem that considers adjustments to an initial routing itinerary when one or more vehicle failures occur during the execution stage and the original plan must be modified. We minimize the operational and schedule disruption costs. Formulations based on mixed‐integer programming are presented to compare different policies in the rerouting phase. A solution strategy is developed when both costs are evaluated and it is necessary to find a solution quickly. Computational tests on a large set of instances compare the different decision‐maker policies.     

An anticipative scheduling approach with controllable processing times

In practice, machine schedules are usually subject to disruptions which have to be repaired by reactive scheduling decisions. The most popular predictive approach in project management and machine scheduling literature is to leave idle times (time buffers) in schedules in coping with disruptions, i.e. the resources will be under-utilized. Therefore, preparing initial schedules by considering possible disruption times along with rescheduling objectives is critical for the performance of rescheduling decisions. In this paper, we show that if the processing times are controllable then an anticipative approach can be used to form an initial schedule so that the limited capacity of the production resources are utilized more effectively. To illustrate the anticipative scheduling idea, we consider a non-identical parallel machining environment, where processing times can be controlled at a certain compression cost. When there is a disruption during the execution of the initial schedule, a match-up time strategy is utilized such that a repaired schedule has to catch-up initial schedule at some point in future. This requires changing machine–job assignments and processing times for the rest of the schedule which implies increased manufacturing costs. We show that making anticipative job sequencing decisions, based on failure and repair time distributions and flexibility of jobs, one can repair schedules by incurring less manufacturing cost. Our computational results show that the match-up time strategy is very sensitive to initial schedule and the proposed anticipative scheduling algorithm can be very helpful to reduce rescheduling costs.     

Completion time variance minimisation on two identical parallel processors

The problem of scheduling jobs to minimise completion time variance (CTV) is a well-known problem in scheduling research. CTV is categorized as a non-regular performance measure and its value may decrease by increasing the job completion times. This objective is relevant in situations where providing uniform service to customers is important, and is in-line with just-in-time philosophy. The problem concerned in this paper is to schedule n jobs on two identical parallel machines to minimise CTV. We consider the unrestricted version of the problem. The problem is said to be restricted when a machine is not allowed to remain idle when jobs are available for processing. It may be necessary to delay the start of job processing on a machine in order to reduce the completion time deviations. This gives rise to the unrestricted version of the problem. We discuss several properties of an optimal schedule to the problem. In this paper, we develop a lower bound on CTV for a known partial schedule and propose a branch and bound algorithm to solve the problem. Optimal solutions are obtained and results are reported.     

Robust and stable flow shop scheduling with unexpected arrivals of new jobs and uncertain processing times

In real scheduling problems, some disruptions and unexpected events may occur. These disruptions cause the initial schedule to quickly become infeasible and non-optimal. In this situation, an appropriate rescheduling method should be used. In this paper, a new approach has been proposed to achieve stable and robust schedule despite uncertain processing times and unexpected arrivals of new jobs. This approach is a proactive–reactive method which uses a two-step procedure. In the first step an initial robust solution is produced proactively against uncertain processing times using robust optimization approach. This initial robust solution is more insensitive against the fluctuations of processing times in future. In the next step, when an unexpected disruption occurs, an appropriate reactive method is adopted to deal with this unexpected event. In fact, in the second step, the reactive approach determines the best modified sequence after any unexpected disruption based on the classical objective and performance measures. The robustness measure is implemented in the reactive approach to increase the performance of the real schedule after disruption. Computational results indicate that this method produces better solutions in comparison with four classical heuristic approaches according to effectiveness and performance of solutions.     

Addressing the N/1 scheduling problem—A heuristic approach

The problem of sequencing n-jobs on one machine (n/1) to minimize maximum job lateness has been the subject of much prior research. Most of this research has been directed at identifying optimal solutions to the problem via algorithmic search techniques. A weakness in employing an algorithm for solving the problem, however, is that lengthy computational times may result because of the necessity of searching n! sequences. By employing a multiple heuristic approach this limitation can be avoided. An optimal or near optimal schedule can be identified in a finite number of steps.This paper describes a multiple heuristic model that is effective more than eighty-ninety percent of the time in providing an optimal schedule for the N/l/L max scheduling program. Ten separate heuristics are described, and the results of testing the heuristics over fifteen hundred and sixty randomly generated problems is presented. Three of the heuristics are combined to form the heuristic-scheduling model.     

Supporting rescheduling using CSP, RMS and POB—an example application

This paper introduces an innovative approach to the problem of rescheduling within manufacturing industry. An example of a manufacturing context that requires rescheduling capability is given (tyre production). The meaning of rescheduling, possible metrics for assessment of rescheduling and the advantages of applying the new techniques are reviewed. Of particular importance is the notion that the technology for providing rescheduling and explanation capabilities is to a large degree problem and context insensitive. The manner in which an original schedule has been created is irrelevant to the use of the technology described, allowing the advantages of the approach to be realized as an add-on facility to any existing scheduling system that fulfills a minimal set of requirements. These advantages are due to the use of a constraint based approach to new schedule creation used in tandem with dependency analysis techniques based on reason maintenance systems (de Kleer, 1986) and partial order backtracking (Ginsberg and McAllister, 1995; Spragg and Kelleher, 1996).     

A Complete 4-parametric complexity classification of short shop scheduling problems

We present a comprehensive complexity analysis of classical shop scheduling problems subject to various combinations of constraints imposed on the processing times of operations, the maximum number of operations per job, the upper bound on schedule length, and the problem type (taking values ??open shop,?? ??job shop,?? ??mixed shop??). It is shown that in the infinite class of such problems there exists a finite basis system that allows one to easily determine the complexity of any problem in the class. The basis system consists of ten problems, five of which are polynomially solvable, and the other five are NP-complete. (The complexity status of two basis problems was known before, while the status of the other eight is determined in this paper.) Thereby the dichotomy property of that parameterized class of problems is established. Since one of the parameters is the bound on schedule length (and the other two numerical parameters are tightly related to it), our research continues the research line on complexity analysis of short shop scheduling problems initiated for the open shop and job shop problems in the paper by Williamson et?al. (Oper. Res. 45(2):288?C294, 1997). We improve on some results of that paper.     

An ILS heuristic for the ship scheduling problem: application in the oil industry

This paper addresses a real‐life rescheduling problem of a pipe‐laying support vessel (PLSV) fleet in charge of subsea oil well connections. The short‐term schedule of these vessels is subject to uncertainties inherent to its operations, resulting in ships idleness or delays in oil production. The objective of this study is to develop methods to support a Brazilian oil and gas company in overcoming impacts caused by operational disruptions, while reaching its planned production level. The PLSV rescheduling problem was treated as an identical parallel machine scheduling problem, where the machines represent the vessels and the jobs are the activities for the subsea well connections. We propose a mathematical programming model and a method based on the iterated local search (ILS) metaheuristic to solve the problem. This paper contributes to this by considering simultaneously setup times, machine eligibility, release dates, due dates, and machine availability. Both methods were applied on 10 instances based on real PLSV data. Taking into account an objective function that measures the operational impact on schedules, the ILS provided an average improvement above 91% in schedules when compared to the initial solution provided by the studied company. The ILS outperformed a mathematical programming model for the problem, in eight instances, within a 30‐minute execution time limit, fitting to the company process.     

Genetic algorithms for match-up rescheduling of the flexible manufacturing systems

Scheduling plays a vital role in ensuring the effectiveness of the production control of a flexible manufacturing system (FMS). The scheduling problem in FMS is considered to be dynamic in its nature as new orders may arrive every day. The new orders need to be integrated with the existing production schedule immediately without disturbing the performance and the stability of existing schedule. Most FMS scheduling methods reported in the literature address the static FMS scheduling problems. In this paper, rescheduling methods based on genetic algorithms are described to address arrivals of new orders. This study proposes genetic algorithms for match-up rescheduling with non-reshuffle and reshuffle strategies which accommodate new orders by manipulating the available idle times on machines and by resequencing operations, respectively. The basic idea of the match-up approach is to modify only a part of the initial schedule and to develop genetic algorithms (GAs) to generate a solution within the rescheduling horizon in such a way that both the stability and performance of the shop floor are kept. The proposed non-reshuffle and reshuffle strategies have been evaluated and the results have been compared with the total-rescheduling method.     

Constraint-specific recovery network for solving airline recovery problems

In this paper, we consider the recovery of an airline schedule after an unforeseen event called disruption, making the planned schedule infeasible. We present a modeling framework that allows the consideration of operational constraints within a Column Generation (CG) scheme. We introduce the general concept of recovery network, generated for each individual unit of the problem, and show how unit-specific constraints are modeled using resources. We fully illustrate the concept by solving the Aircraft Recovery Problem (ARP) with maintenance planning, we give some insights into applying the model to the Passenger Recovery Problem (PRP) and we present computational results on real data.