A two stage heuristic algorithm for the integrated aircraft and crew schedule recovery problems

Airline disruptions incurred huge cost for airlines and serious inconvenience for travelers. In this paper, we study the integrated aircraft and crew schedule recovery problem. A two stage heuristic algorithm for the integrated recovery problem is proposed. In the first stage, the integrated aircraft recovery and flight-rescheduling model with partial crew consideration is built. This model is based on the traditional multi-commodity network model for the aircraft schedule recovery problem. The objective of this model also includes minimization of the original crew connection disruption. In the second stage, the integrated crew schedule recovery and flight re-scheduling model with partial aircraft consideration is built. We proposed a new multi-commodity model for the crew schedule recovery. The main advantage of such model is that it is much more efficient to integrate the flight-scheduling and aircraft consideration. New constraints are incorporated to guarantee that the aircraft connections generated in the stage 1 are still feasible. Two stages are run iteratively until no improvement can be achieved. Experimental results show that our method can provide better recovery solutions compared with the benchmark algorithms.     

A disruption recovery plan in a three-stage production-inventory system

This paper proposes a recovery plan for managing disruptions in a three-stage production-inventory system under a mixed production environment. First, a mathematical model is developed to deal with a disruption at any stage while maximizing total profit during the recovery-time window. The model is solved after the occurrence of a disruption event, with changed data used to generate a revised plan. We also propose a new and efficient heuristic for solving the developed mathematical model. Second, multiple disruptions are considered, where a new disruption may or may not affect the recovery plans of earlier disruptions. The heuristic, developed for a single disruption, is extended to deal with a series of disruptions so that it can be implemented for disruption recovery on a real-time basis. We compare the heuristic solutions with those obtained by a standard search algorithm for a set of randomly generated disruption test problems, and that show the consistent performance of our developed heuristic with lower computational times. Finally, some numerical examples and a real-world case study are presented to demonstrate the benefits and usefulness of our proposed approach.     

A reactive mitigation approach for managing supply disruption in a three-tier supply chain

In this paper, we develop a quantitative reactive mitigation approach for managing supply disruption for a supply chain. We consider a three-tier supply chain system with multiple raw material suppliers, a single manufacturer and multiple retailers, where the system may face sudden disruption in its raw material supply. First, we develop a mathematical model that generates a recovery plan after the occurrence of a single disruption. Here, the objective is to minimize the total cost during the recovery time window while being subject to supply, capacity, demand, and delivery constraints. We develop an efficient heuristic to solve the model for a single disruption. Second, we also consider multiple disruptions, where a new disruption may or may not affect the recovery plans of earlier disruptions. We also develop a new dynamic mathematical and heuristic approach that is capable of dealing with multiple disruptions, after the occurrence of each disruption as a series, on a real-time basis. We compare the heuristic solutions with those obtained by a standard search algorithm for a set of randomly generated disruption test problems, which shows the consistent performance of our heuristic. Finally, a simulation model is developed to analyze the effect of randomly generated disruption events that are not known in advance. The numerical results and many random experiments are presented to explain the usefulness of the developed models and methodologies.     

Formation of general GT cells: an operation-based approach

In this paper, we study the formation of general Group Technology cells based on the operation requirements of parts and operation capabilities of machines. Parts are first grouped into families by using a similarity coefficient based on common operation types. An integer model is then developed to solve the problem of machine group selection. The model takes into account machine cost, variable production cost, setup cost, and intracell material handling cost. A greedy heuristic, a minimum increment heuristic and a simulated annealing heuristic are proposed for solving the model more efficiently. The computational results have shown that the heuristic methods perform well when compared to the optimal solutions. The effect of changing cost structure on the performance of heuristic procedures is also investigated.     

A supply chain disruption recovery strategy considering product change under COVID-19

A recent global outbreak of Corona Virus Disease 2019 (COVID-19) has led to massive supply chain disruption, resulting in difficulties for manufacturers on recovering their supply chains in a short term. This paper presents a supply chain disruption recovery strategy with the motivation of changing the original product type to cope with that. In order to maximize the total profit from product changes, a mixed integer linear programming (MILP) model is developed with combining emergency procurement on the supply side and product changes by the manufacturer as well as backorder price compensation on the demand side. The model uses a heuristic algorithm based on ILOG CPLEX toolbox. Experimental results show that the proposed disruption recovery strategy can effectively reduce the profit loss of manufacturer due to late delivery and order cancellation. It is observed that the impact of supply chain disruptions is reduced. The proposed model can offer a potentially useful tool to help the manufacturers decide on the optimal recovery strategy whenever the supply chain system experiences a sudden massive disruption.     

染缸排产建模及滑动时间窗启发式调度算法

针对染缸排产问题约束复杂、任务规模大、排产效率要求高的特点,为了提高问题模型和算法在实际场景中的适用性,建立了染缸排产增量调度模型,提出了滑动时间窗启发式调度（STWS）算法。该算法以最小化延误代价、洗缸成本、染缸切换成本为优化目标,使用启发式调度规则,按照优先级顺序调度产品;对于每个产品的调度,先用动态拼缸算法和拆缸算法进行批次划分,然后调用批次最佳排序算法调度批次。使用某染纱企业车间实际生产数据仿真调度,所提算法可在10 s内完成月度计划的调度。相对于人工排产方式,所提算法提高了排产效率,显著优化了三个目标,在增量调度中洗缸成本和染缸切换成本也有明显优化。实验结果表明所提算法具有很好的调度能力。     

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.     

Integrated model for software component selection with simultaneous consideration of implementation and verification

One important objective of component-based software engineering is the minimization of the development cost of software products. Thus, the costs of software component implementation and verification, which may involve substantial expenses while under development, should be reduced. In addition, the costs for these processes should not be considered individually, but in an integrated manner, to further reduce development cost. In the current paper, an integrated decision model is proposed to assist decision-makers in selecting reuse scenarios for components used for implementation and in simultaneously determining the optimal number of test cases for verification. An objective of the model is the minimization of development cost, while satisfying the required system and reliability requirements. The Lagrange relaxation decomposition (LRD) method with heuristics was developed to solve integrated decision problems. Based on LRD, the nonlinear model is condensed into a 0–1 knapsack problem for the subproblem on reuse scenario selection and an integer knapsack problem for the subproblem on the determination of the optimal number of tests. Combined with the Lagrange multiplier-determined heuristic, the proposed algorithm can determine the global optimum solution. Simulations of varying sizes for problems and sensitivity analyses were conducted, and the results indicate that LRD is more effective than previous methods in determining global optimal solutions for the integrated decision problem.     

Review of real-time vehicle schedule recovery methods in transportation services

This paper presents a comprehensive review on methods for real-time schedule recovery in transportation services. The survey concentrates on published research on recovery of planned schedules in the occurrence of one or several severe disruptions such as vehicle breakdowns, accidents, and delays. Only vehicle assignment and rescheduling are reviewed; crew scheduling and passenger logistics problems during disruptions are not. Real-time vehicle schedule recovery problems (RTVSRP) are classified into three classes: vehicle rescheduling, for road-based services, train-based rescheduling, and airline schedule recovery problems. For each class, a classification of the models is presented based on problem formulations and solution strategies. The paper concludes that RTVSRP is a challenging problem that requires quick and good quality solutions to very difficult and complex situations, involving several different contexts, restrictions, and objectives. The paper also identifies research gaps to be investigated in the future, stimulating research in this area.     

An integrated replenishment model with quantity discounts, reentry and downward substitution for control wafers

This paper considers control wafers replenishment problem in wafer fabrication factories. A dynamic lot-sizing replenishment problem with reentry and downward substitution is examined in a pulling control production environment. The objective is to set the inventory level so as to minimize the total cost of control wafers, where the costs include order cost, purchase cost, setup cost, production cost and holding cost, while maintaining the same level of production throughput. In addition, purchase quantity discounts and precise inventory level are considered in the replenishment model. The control wafers replenishment problem is first constructed as a network, and is then transformed into a mixed integer programming model. Lastly, an efficient heuristic algorithm is proposed for solving large-scale problems. A numerical example is given to illustrate the practicality for empirical investigation. The results demonstrate that the proposed mixed integer programming model and the heuristic algorithm are effective tools for determining the inventory level of control wafers for multi-grades in multi-periods.     

Decomposition heuristic to minimize total cost in a multi-level supply chain network

In this paper, the distribution planning model for the multi-level supply chain network is studied. Products which are manufactured at factory are delivered to customers through warehouses and distribution centers for the given customer demands. The objective function of suggested model is to minimize logistic costs such as replenishment cost, inventory holding cost and transportation cost. A mixed integer programming formulation and heuristics for practical use are suggested. Heuristics are composed of two steps: decomposition and post improving process. In the decomposition heuristics, the problems are solved optimally only considering the transportation route first by the minimum cost flow problem, and the replenishment plan is generated by applying the cost-saving heuristic which was originally suggested in the manufacturing assembly line operation, and integrating with the transportation plan. Another heuristic, in which the original model is segmented due to the time periods, and run on a rolling horizon based method, is suggested. With the post-improving process using tabu search method, the performances are evaluated, and it was shown that solutions can be computed within a reasonable computation time by the gap of about 10% in average from the lower bound of the optimal solutions.     

Covering a graph with cycles

In several areas of engineering and telecommunications, it is necessary to determine a least cost cover of a graph by means of cycles. We propose a highly efficient yet simple heuristic for this difficult problem. On test problems it consistently produces optimal or near optimal solutions.This article describes a lower bounding procedure and heuristics for the Cycle Cover Problem which consists of determining a least cost cover of an undirected graph with simple cycles. Applications of this problem arise in network design and in telecommunications. Computational results demonstrate the quality of the proposed heuristics. On 100 vertex graphs, the best of these consistently produces optimal or quasi-optimal solutions.     

基于多目标遗传算法的集装箱码头泊位—岸桥分配问题研究

为获得合理的集装箱码头泊位—岸桥分配方案,建立了以最小化船舶在港时间和码头生产成本为目标的优化模型。提出一种多目标遗传算法用于求解该模型,算法中采用染色体组的方式表示可行解,给出了多个约束条件下的交叉算子运算规则,个体的各目标值结合岸桥分配启发式算法求得,并应用Pareto分级方法进行适应度值评价;同时给出了最终实施方案的选择策略。试验算例表明,与单目标优化相比,提出的优化方法能获得使码头综合效益较大的满意解。     

Replica placement algorithms for mobile transaction systems

In distributed mobile systems, communication cost and disconnections are major concerns. In this paper, we address replica placement issues to achieve improved performance for systems supporting mobile transactions. We focus on handling correlated data objects and disconnections. Frequently, requests and/or transactions issued by mobile clients may access multiple data objects and should be considered together in terms of replica allocation. We discuss the replication cost model for correlated data objects and show that the problem of finding an optimal solution is NP. We further adjust the replication cost model for disconnections. A heuristic "expansion-shrinking" algorithm is developed to efficiently make replica placement decisions. The algorithm obtains near optimal solutions for the correlated data model and yields significant performance gains when disconnection is considered. Experimental studies show that the heuristic expansion-shrinking algorithm significantly outperforms the general frequency-based replication schemes.     

Modeling supplier selection and the use of option contracts for global supply chain design

As supply chains become more and more dependent on the efficient movement of materials among facilities that are geographically dispersed there is more opportunity for disruption. One of the common disruptions is the loss of production capability at supplier sites. We formulate a two-stage stochastic program and a solution procedure to optimize supplier selection to hedge against these disruptions. This model allows for the effective quantitative exploration of the trade-off between cost and risks to support improved decision-making in global supply chain design. A realistic case study is explored.     

Parallel machine match-up scheduling with manufacturing cost considerations

Many scheduling problems in practice involve rescheduling of disrupted schedules. In this study, we show that in contrast to fixed processing times, if we have the flexibility to control the processing times of the jobs, we can generate alternative reactive schedules considering the manufacturing cost implications in response to disruptions. We consider a non-identical parallel machining environment where processing times of the jobs are compressible at a certain manufacturing cost, which is a convex function of the compression on the processing time. In rescheduling it is highly desirable to catch up the original schedule as soon as possible by reassigning the jobs to the machines and compressing their processing times. On the other hand, one must also keep the manufacturing cost due to compression of the jobs low. Thus, one is faced with a tradeoff between match-up time and manufacturing cost criteria. We introduce alternative match-up scheduling problems for finding schedules on the efficient frontier of this time/cost tradeoff. We employ the recent advances in conic mixed-integer programming to model these problems effectively. We further provide a fast heuristic algorithm driven by dual prices of convex subproblems for generating approximate efficient schedules.     

Capacity and flexibility planning of an economical manufacturing system

This paper presents a simple dynamic model for determining the capacity and the flexibility of a manufacturing system over a finite planning horizon. We consider a problem that arises from the development phase of an investment plan for an economical manufacturing system. The objective is to minimize the total cost associated with the capacity expansion, flexibility expansion and operation. This problem is formulated as an integer program. A Lagrangian heuristic is developed for determining a near optimal solution to this integer program. Finally, we show how to incorporate aggregate production planning into the model.Based on a presentation given at the ORSA/TIMS Miami meeting in 1986.     

Developing software for generating pouring schedules for steel foundries

The authors have been involved in an industry-wide project whose goal is to improve the production systems of steel foundries. As a part of this effort, we have studied the process by which the foundries develop their daily pouring schedule. Typically, the foundries are unable to consider the impact of their pouring schedule on downstream operations because developing a feasible schedule is a labor-intensive task involving numerous constraints. To address this, the authors are working with Harrison Steel to develop software that can both automate the current scheduling process and improve it by estimating the impact of the pouring schedule on downstream work-in-process (WIP) inventory levels. An integer programming model is described that minimizes a comprehensive cost function that includes the costs of pattern tooling set-up, late delivery, WIP inventory, and under-utilization of assets. The software implements a heuristic that finds multiple solutions to this integer program, each of which corresponds to a feasible schedule. Computational tests reveal that the software is capable of handling realistically sized scheduling problems in a reasonable amount of time. Upon its completion, this system could be extended for implementation at many other steel foundries.     

Heuristic procedures for reactive project scheduling

This paper describes new heuristic reactive project scheduling procedures that may be used to repair resource-constrained project baseline schedules that suffer from multiple activity duration disruptions during project execution. The objective is to minimize the deviations between the baseline schedule and the schedule that is actually realized.We discuss computational results obtained with priority-rule based schedule generation schemes, a sampling approach and a weighted-earliness tardiness heuristic on a set of randomly generated project instances.     

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.