An approach to predictive-reactive scheduling of parallel machines subject to disruptions

In this paper, a new predictive-reactive approach to a parallel machine scheduling problem in the presence of uncertain disruptions is presented. The approach developed is based on generating a predictive schedule that absorbs the effects of possible uncertain disruptions through adding idle times to the job processing times. The uncertain disruption considered is material shortage, described by the number of disruption occurrences and disruption repair period. These parameters are specified imprecisely and modelled using fuzzy sets. If the impact of a disruption is too high to be absorbed by the predictive schedule, a rescheduling action is carried out. This approach has been applied to solving a real-life scheduling problem of a pottery company.     

双机成比例无等待流水线重调度干扰管理研究

针对由异速机构成的双机成比例无等待流水线的加工特点,研究了机器扰动工况下的生产重调度问题,提出了兼顾初始调度目标(最小化制造期)和扰动修复目标(最小化工件滞后时间和)的干扰管理方法。在最短加工时间优先(SPT)排序规则的最优解特性分析基础上,证明了右移初始加工时间表是事后干扰管理的最优调度方案,建立了基于SPT规则的事前干扰管理模型,设计了基于理想点趋近的多目标处理策略,提出了离散量子微粒群优化与局部搜索机制相结合的启发式模型求解算法。算例实验结果表明,本文提出的干扰管理模型和算法是有效的。     

考虑应急设施中断风险与防御的可靠性选址模型研究

为提高应急设施运行的可靠性和抵御中断风险的能力, 研究中断情境下的应急设施选址-分配决策问题。扩展传统无容量限制的固定费用选址模型, 从抵御设施中断的视角和提高服务质量的视角建立选址布局网络的双目标优化模型, 以应急设施的建立成本和抵御设施中断的加固成本最小为目标, 以最大化覆盖服务质量水平为目标, 在加固预算有限及最大最小容量限制约束下, 构建中断情境下应急设施的可靠性选址决策优化模型。针对所构建模型的特性利用非支配排序多目标遗传算法(NSGA-Ⅱ)求解该模型, 得到多目标的Pareto前沿解集。以不同的算例分析和验证模型和算法的可行性。在获得Pareto前沿的同时对不同中断概率进行灵敏度分析, 给出Pareto最优解集的分布及应急设施选址布局网络的拓扑结构。     

考虑加工效率变化的变速机干扰管理研究

在变速机生产排序中, 受来自企业外部可改变机器加工效率的突发性干扰事件影响, 初始最小化企业生产成本的加工时间表不再最优,需要对其调整并在生产成本和干扰事件扰动之间进行权衡。建立了同时考虑生产成本和干扰事件扰动的重排序模型, 生产成本为所有机器的负载之和, 干扰事件的扰动为工件在不同机器之间重新安排所产生的运输费用和。设计了求解该重排序问题有效前沿的算法, 以及利用决策者对两个目标的偏好将双目标转化成一个二元非线性函数后, 求解优化该函数的有效解的算法。通过数值算例验证与整个有效前沿相比,优化二元函数的算法只需搜索部分有效前沿即可求出最优解,降低了有效解的搜索比例和运行时间,提高了干扰管理问题的处理效率。     

Predictive–reactive scheduling on a single resource with uncertain future jobs

We consider a scheduling problem where the firm must compete with other firms to win future jobs. Uncertainty arises as a result of incomplete information about whether the firm will win future jobs at the time the firm must create a predictive (planned) schedule. In the predictive schedule, the firm must determine the amount of planned idle time for uncertain jobs and their positions in the schedule. When the planned idle time does not match the actual requirements, certain schedule disruptions occur. The firm seeks to minimize the sum of expected tardiness cost, schedule disruption cost, and wasted idle time cost. For the special case of a single uncertain job, we provide a simple algorithm for the optimal planned idle time and the best reactive method for schedule disruptions. For the case of multiple uncertain jobs, a heuristic dynamic programming approach is presented.     

单机排序中关于完工前总损失的应急管理

该文研究了扰动环境下的关于完工前总损失的单机排序问题, 也就是这样一个问题: 在时刻 t , 一部分工件已经完工了, 一个扰动发生了, 在这种情形下, 原来的排序已经不是最优排序甚至是不可行排序了. 因此就需要对未完成的工件找一个新的排序. 作者采用的方法与大多数重新排序问题所不同的是: 模型里包含了原始排序与新排序之间的偏差所造成的损失. 作者主要研究了在原始排序中加权最短加工时间规则(WSPT)是最优排序的情形. 根据扰动的类型, 应急管理策略的类型以及目标函数, 研究了几个问题. 对于每个问题, 作者找到了最优排序或者得出了一些重要结果.     

A rolling horizon approach for disruption management of railway rolling stock

This paper deals with real-time disruption management of rolling stock in passenger railway transportation. We describe a generic framework for dealing with disruptions of railway rolling stock schedules. The framework is presented as an online combinatorial decision problem, where the uncertainty of a disruption is modeled by a sequence of information updates. To decompose the problem and to reduce the computation time, we propose a rolling horizon approach: rolling stock decisions are only considered if they are within a certain time horizon from the time of rescheduling. The schedules are then revised as time progresses and new information becomes available. We extend an existing model for rolling stock scheduling to the specific requirements of the real-time situation, and we apply it in the rolling horizon framework. We perform computational tests on instances constructed from real-life cases of Netherlands Railways (NS), the main operator of passenger trains in the Netherlands. We explore the consequences of different settings of the approach for the trade-off between solution quality and computation time.     

Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria

In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and the schedule deviation measures. The efficiency measure is the total flow time, and the schedule deviation measure is the total disruption cost caused by the differences between the initial and current schedules. We provide polynomial-time solution methods to the following hierarchical optimization problems: minimizing total disruption cost among the minimum total flow time schedules and minimizing total flow time among the minimum total disruption cost schedules. We propose exponential-time algorithms to generate all efficient solutions and to minimize a specified function of the measures. Our extensive computational tests on large size problem instances have revealed that our optimization algorithm finds the best solution by generating only a small portion of all efficient solutions.     

A new constructive heuristic for the flowshop scheduling problem

This paper presents a simple constructive heuristic (HFC) for the flowshop makespan problem which is capable of producing non-permutation schedules when it deems it appropriate. HFC determines the order of any two jobs in the final schedule based on their order in all two-machine problems embedded in the problem. Computational experiments indicate that HFC performs as well as NEH which is the currently best available constructive heuristic on problems where a permutation schedule is expected to be optimal. However, HFC outperforms NEH on problems where a non-permutation schedule may be optimal.     

基于重新排序的退化工件最小化总延误时间问题

考虑了错位限制下的含有退化工件的重新排序问题,即工件的实际加工时间看作是工件开工时间的线性函数．重新排序就是在原始工件已经按照某种规则使目标函数达到最优时有一新工件集到达,新工件的安排使得原始工件重新排序进而产生错位．研究了最大序列错位和总序列错位限制下的退化工件最小化总延误时间问题,其最优排序的结构性质是使得原始工件集和新工件集中的工件是按加工率αj非减的序列排列,基于此通过分阶段排序和动态规划方法给出了两个问题的多项式时间的最优算法．     

基于重新排序时间错位限制下的最小化总完工时间的平行分批排序（英文）

In the rescheduling on a single machine, a set of the original jobs has already been scheduled, in order to make a given objective function is optimal. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. A batching machine is a machine that can handle up to some jobs simultaneously. In this paper,we consider the total completion time under a limit on the sequence disruptions for parallel batching based on rescheduling. For the parallel batching problem based on rescheduling, we research the properties of feasible schedules and optimal schedules on the total completion time under a limit on the maximum time disruptions or total time disruptions, in which the jobs are sequenced in SPT order, and give out the pseudo-polynomial time algorithms on the number of jobs and the processing time of jobs by applying the dynamic programming method.     

Two-machine open shop scheduling with special transportation times

The paper considers a problem of scheduling n jobs in a two-machine open shop to minimise the makespan, provided that preemption is not allowed and the interstage transportation times are involved. In general, this problem is known to be NP-hard. We present a linear time algorithm that finds an optimal schedule if no transportation time exceeds the smallest of the processing times. We also describe an algorithm that creates a heuristic solution to the problem with job-independent transportation times. Our algorithm provides a worst-case performance ratio of 8/5 if the transportation time of a job depends on the assigned processing route. The ratio reduces to 3/2 if all transportation times are equal.     

序列错位限制下最小化完工时间和的继列分批重新排序

在单机分批排序中,一个原始工件集已经分好批排好顺序,使得给定的目标函数最小.当一个新的工件集到来时,决策者需要插入这些新工件到原来的顺序中,这样使得原始工件就会产生一些错位.但为了满足对原始工件集的要求而不过分的打乱它们的顺序的条件下,使得新的目标值为最优.本文主要研究的是在序列错位量限制的条件下,继列分批最小化总完工时间的重新排序问题,对于最大序列错位和总序列错位的不同约束情况下,研究可行排序和最优排序的结构性质,进而设计了它们的多项式时间算法.     

带折扣因子的单机干扰管理研究

针对可预见的干扰管理问题,考虑单机环境下,加权折扣最短加工时间优先(WDSPT)序为原目标的最优加工次序,研究了如何对初始加工时间表进行修改。在干扰事件影响下,初始加工时间表将不再是最优,甚至不再可行。和大多数重排序研究不同,构建了同时考虑原目标和由干扰事件造成的扰动目标的重排序模型,并基于理想点法提出一种动态规划算法来求解所建模型中的双目标排序问题。最后通过一个数值算例来说明该重调度模型对于求解带折扣因子的单机干扰管理问题是有效的。     

工件延误和可拒绝下的单机重新排序问题的近似方案

研究工件延误产生干扰且延误工件可拒绝下的单机重新排序问题.在该问题中,给定计划在零时刻到达的一个工件集需在一台机器上加工,工件集中的每个工件有它的加工时间和权重,在工件正式开始加工前,按照最短赋权加工时间优先的初始排序已经给定,目标函数是极小化赋权完工时间和,据此每个工件的承诺交付截止时间也给定.然而,在工件正式开始加...     

相容工件系统的最小化最大延迟与误工和的重新排序

在单机重新排序问题中,一个原始工件集已经排好顺序,使得给定的目标函数最小．当一个新的工件集到来时就会产生一些错位,决策者需要插入新工件到原来排序中而还不能过分打乱它们的顺序．该论文首先研究了当工件加工时间和工期相容时,在错位量限制的条件下最小化最大延迟问题;也研究了当工件加工时间相同或工件工期相同时,在错位量限制的条件下最小化误工和问题．对这些问题,给出了好的算法．     

Production and shipment lot sizing in a vendor–buyer supply chain with transportation cost

Previous research on the joint vendor–buyer problem focused on the production shipment schedule in terms of the number and size of batches transferred between the two parties. It is a fact that transportation cost is a major part of the total operational cost. However, in most joint vendor–buyer models, the transportation cost is only considered implicitly as a part of fixed setup or ordering cost and thus is assumed to be independent of the size of the shipment. As such, the effect of the transportation cost is not adequately reflected in final planning decisions. There is a need for models involving transportation cost explicitly for better decision-making. In this study we analyze the vendor–buyer lot-sizing problem under equal-size shipment policy. We introduce the complete solution of the problem in an explicit and extended manner that has not existed in the literature. We incorporate transportation cost explicitly into the model and develop optimal solution procedures for solving the integrated models. All-unit-discount transportation cost structures with and without over declaration have been considered. Numerical examples are presented for illustrative purpose.     

Large-scale optimization planning methods for the distribution of United States army munitions

Coordinating the distribution of ammunition and scheduling strategic transportation resources during military contingency operations is a complex process. This paper presents a large-scale optimization-based planning method that uses column generation to schedule the movement of ammunition and transportation resources through a time-space network representation of the distribution system. The optimization-based planner is initialized using a feasible solution generated by a heuristic planning method. Both the optimization-based planner and the heuristic planner generate plans with improved ship utilization and delivery tardiness values as compared to plans generated using current planning techniques. In addition, the heuristic planner is implemented within a closed-loop planning and control framework, and is used to generate plans on a rolling horizon basis.     

Rescheduling with new orders and general maximum allowable time disruptions

We study the rescheduling with new orders on a single machine under the general maximum allowable time disruptions. Under the restriction of general maximum allowable time disruptions, each original job has an upper bound for its time disruption (regarded as the maximum allowable time disruption of the job), or equivalently, in every feasible schedule, the difference of the completion time of each original job compared to that in the pre-schedule does not exceed its maximum allowable time disruption. We also consider a stronger restriction which additionally requires that, in a feasible schedule, the starting time of each original job is not allowed to be scheduled smaller than that in the pre-schedule. Scheduling objectives to be minimized are the maximum lateness and the total completion time, respectively, and the pre-schedules of original jobs are given by EDD-schedule and SPT-schedule, respectively. Then we have four problems for consideration. For the two problems for minimizing the maximum lateness, we present strong NP-hardness proof, provide a simple 2-approximation polynomial-time algorithm, and show that, unless \(\text {P}= \text {NP}\), the two problems cannot have an approximation polynomial-time algorithm with a performance ratio less than 2. For the two problems for minimizing the total completion time, we present strong NP-hardness proof, provide a simple heuristic algorithm, and show that, unless \(\text {P}= \text {NP}\), the two problems cannot have an approximation polynomial-time algorithm with a performance ratio less than 4/3. Moreover, by relaxing the maximum allowable time disruptions of the original jobs, we present a super-optimal dual-approximation polynomial-time algorithm. As a consequence, if the maximum allowable time disruption of each original job is at least its processing time, then the two problems for minimizing the total completion time are solvable in polynomial time. Finally, we show that, under the agreeability assumption (i.e., the nondecreasing order of the maximum allowable time disruptions of the original jobs coincides with their scheduling order in the pre-schedule), the four problems in consideration are solvable in polynomial time.     

Planning and consolidating shipments from a warehouse

A typical warehouse or distribution centre ships material to various customer locations across the country, using various modes of transportation. Each mode has different constraints on size of shipment, different cost structures and different transportation times. Typically, for a given warehouse there are certain customer locations that receive frequent shipments of material. It is often possible, therefore, for the warehouse to consolidate different orders for the same customer location into a single shipment. The transportation mode and the day of shipment must be chosen such that the consolidated shipment meets the size constraints and arrives within an agreed-upon ‘delivery window’. In preparing a warehouse distribution plan, a planner seeks to achieve transportation economies of scale (by consolidating two or more orders into fewer shipments) while levelling the workload on warehouse resources and ensuring that material arrives at a customer location during the acceptable delivery window.The problem of deciding what shipments to make daily can be formulated as a set partitioning problem with side constraints. This paper describes a heuristic solution approach for this problem. Computational experiments using actual warehouse select activity indicate that, for moderate-size problems, the heuristic produces solutions with transportation costs that are within a few percent of optimal. Larger problems found in practice are generally too large to be solved by optimal algorithms; the heuristic easily handles such problems. The heuristic has been integrated into the transportation planning system of a leading distributor of telecommunications products.