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.     

Schedule execution for two-machine flow-shop with interval processing times

This paper addresses the issue of how to best execute the schedule in a two-phase scheduling decision framework by considering a two-machine flow-shop scheduling problem in which each uncertain processing time of a job on a machine may take any value between a lower and upper bound. The scheduling objective is to minimize the makespan. There are two phases in the scheduling process: the off-line phase (the schedule planning phase) and the on-line phase (the schedule execution phase). The information of the lower and upper bound for each uncertain processing time is available at the beginning of the off-line phase while the local information on the realization (the actual value) of each uncertain processing time is available once the corresponding operation (of a job on a machine) is completed. In the off-line phase, a scheduler prepares a minimal set of dominant schedules, which is derived based on a set of sufficient conditions for schedule domination that we develop in this paper. This set of dominant schedules enables a scheduler to quickly make an on-line scheduling decision whenever additional local information on realization of an uncertain processing time is available. This set of dominant schedules can also optimally cover all feasible realizations of the uncertain processing times in the sense that for any feasible realizations of the uncertain processing times there exists at least one schedule in this dominant set which is optimal. Our approach enables a scheduler to best execute a schedule and may end up with executing the schedule optimally in many instances according to our extensive computational experiments which are based on randomly generated data up to 1000 jobs. The algorithm for testing the set of sufficient conditions of schedule domination is not only theoretically appealing (i.e., polynomial in the number of jobs) but also empirically fast, as our extensive computational experiments indicate.     

The dominance digraph as a solution to the two-machine flow-shop problem with interval processing times

The flow-shop minimum-length scheduling problem with n jobs processed on two machines is addressed where processing times are uncertain: lower and upper bounds for the random processing time are given before scheduling, but its probability distribution between these bounds is unknown. For such a problem, there often does not exist a dominant schedule that remains optimal for all possible realizations of the job processing times, and we look for a minimal set of schedules that is dominant. Such a minimal dominant set of schedules may be represented by a dominance digraph. We investigate useful properties of such a digraph.     

Time slack-based techniques for robust project scheduling subject to resource uncertainty

The resource-constrained project scheduling problem (RCPSP) has been the subject of a great deal of research during the previous decades. This is not surprising given the high practical relevance of this scheduling problem. Nevertheless, extensions are needed to be able to cope with situations arising in practice such as multiple activity execution modes, activity duration changes and resource breakdowns. In this paper we analytically determine the impact of unexpected resource breakdowns on activity durations. Furthermore, using this information we develop an approach for inserting explicit idle time into the project schedule in order to protect it as well as possible from disruptions caused by resource unavailabilities. This strategy will be compared to a traditional simulation-based procedure and to a heuristic developed for the case of stochastic activity durations.     

The dynamic vehicle rescheduling problem

The pre-planned schedules of a transportation company are often disrupted by unforeseen events. As a result of a disruption, a new schedule has to be produced as soon as possible. This process is called the vehicle rescheduling problem, which aims to solve a single disruption and restore the order of transportation. However, there are multiple disruptions happening over a “planning unit” (usually a day), and all of them have to be addressed to achieve a final feasible schedule. From an operations management point of view the quality of the final solution has to be measured by the combined quality of every change over the horizon of the “planning unit”, not by evaluating the solution of each disruption as a separate problem. The problem of finding an optimal solution where all disruptions of a “planning unit” are addressed will be introduced as the dynamic vehicle rescheduling problem (DVRSP). The disruptions of the DVRSP arrive in an online manner, but giving an optimal final schedule for the “planning unit” would mean knowing all information in advance. This is not possible in a real-life scenario, which means that heuristic solution methods have to be considered. In this paper, we present a recursive and a local search algorithm to solve the DVRSP. In order to measure the quality of the solutions given by the heuristics, we introduce the so-called quasi-static DVRSP, a theoretical problem where all the disruptions are known in advance. We give two mathematical models for this quasi-static problem, and use their optimal solutions to evaluate the quality of our heuristic results. The heuristic methods for the dynamic problem are tested on different random instances.     

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

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

Robust scheduling and robustness measures for the discrete time/cost trade-off problem

Projects are often subject to various sources of uncertainties that have a negative impact on activity durations and costs. Therefore, it is crucial to develop effective approaches to generate robust project schedules that are less vulnerable to disruptions caused by uncontrollable factors. In this paper, we investigate the robust discrete time/cost trade-off problem, which is a multi-mode project scheduling problem with important practical relevance. We introduce surrogate measures that aim at providing an accurate estimate of the schedule robustness. The pertinence of each proposed measure is assessed through computational experiments. Using the insights revealed by the computational study, we propose a two-stage robust scheduling algorithm. Finally, we provide evidence that the proposed approach can be extended to solve a complex robust problem with tardiness penalties and earliness revenues.     

Multi-objective genetic algorithm for single machine scheduling problem under fuzziness

This paper presents a new multi-objective approach to a single machine scheduling problem in the presence of uncertainty. The uncertain parameters under consideration are due dates of jobs. They are modelled by fuzzy sets where membership degrees represent decision maker’s satisfaction grade with respect to the jobs’ completion times. The two objectives defined are to minimise the maximum and the average tardiness of the jobs. Due to fuzziness in the due dates, the two objectives become fuzzy too. In order to find a job schedule that maximises the aggregated satisfaction grade of the objectives, a hybrid algorithm that combines a multi-objective genetic algorithm with local search is developed. The algorithm is applied to solve a real-life problem of a manufacturing pottery company.     

时间窗变动的车辆调度干扰管理模型与算法

针对客户时间窗变动对原物流配送车辆调度方案造成干扰的问题,运用干扰管理思想,分析干扰事件对路径、成本和服务时间三个方面的影响,对其干扰程度加以度量;以该干扰事件对原方案造成的广义费用偏离最小为目标,建立客户时间窗变动的干扰管理模型,通过判断客户时间窗变动对原方案是否产生影响进行干扰辨识,并基于该干扰辨识结果,设计基于禁忌搜索新的调度算法;算例不仅验证了模型和算法的有效性,而且,敏感性分析也验证了其对各种不同价值货物的适用性。实验结果表明,本文提出的干扰管理模型可以全面地刻画干扰对原方案的影响,干扰处理方法优于全局重调度方法,且能够在更短时间内生成满意的物流配送车辆调度调整方案。     

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

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

Solving project scheduling problem with the philosophy of fuzzy random programming

Project scheduling problem is to determine the schedule of allocating resources to achieve the trade-off between the project cost and the completion time. In real projects, the trade-off between the project cost and the completion time, and the uncertainty of the environment are both considerable aspects for managers. Due to the complex external environment, this paper considers project scheduling problem with coexisted uncertainty of randomness and fuzziness, in which the philosophy of fuzzy random programming is introduced. Based on different ranking criteria of fuzzy random variables, three types of fuzzy random models are built. Besides, a searching approach by integrating fuzzy random simulations and genetic algorithm is designed for searching the optimal schedules. The goal of the paper is to provide a new method for solving project scheduling problem in hybrid uncertain environments.     

Parallel-machine scheduling under potential disruption

In this paper, we study a parallel-machine scheduling problem that arises in a disruptive environment. Such a problem deals with a situation when there is a possibility that a disruption will occur at a particular time and if it happens all machines will become unavailable for certain duration with a certain probability. Our goal is to schedule the jobs so that the expected sum of weighted completion times is minimized. We provide pseudo-polynomial time algorithms to solve the problem to optimality. This research is supported in part by Hong Kong RGC Earmark grant HKUST 6145/03E.     

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.     

Resource-constrained job scheduling with recyclable resources

In resource-constrained project scheduling problems, resources are typically classified as being either renewable, non-renewable, or doubly-constrained. A new resource classification, recyclable, is introduced. Notation and a generalized problem formulation are developed for resource-constrained job scheduling problems where resources are recyclable. This foundation is then used for studying the single-machine scheduling problem with tooling constraints. For a given set of jobs, the problem is to find the job sequence, tool type quantities, and tool recycling schedule such that the sum of job completion times and quantity of tools allocated are both minimized. Two solution approaches are developed, and examples are used to compare and contrast the approaches. The results indicate that the ‘traditional’ job scheduling approach (i.e. schedule jobs first, then tools) can lead to sub-optimal solutions. Furthermore, by scheduling jobs and tools simultaneously, it may be possible to attain a given level of performance with fewer tools.     

Bilevel programming approach applied to the flow shop scheduling problem under fuzziness

This paper presents a fuzzy bilevel programming approach to solve the flow shop scheduling problem. The problem considered here differs from the standard form in that operators are assigned to the machines and imposing a hierarchy of two decision makers with fuzzy processing times. The shop owner considered higher level and assigns the jobs to the machines in order to minimize the flow time while the customer is the lower level and decides on a job schedule in order to minimize the makespan. In this paper, we use the concepts of tolerance membership function at each level to define a fuzzy decision model for generating optimal (satisfactory) solution for bilevel flow shop scheduling problem. A solution algorithm for solving this problem is given. Mathematics Subject Classification: 90C70, 90B36, 90C99     

Project schedule performance under general mode implementation disruptions

This paper presents a simulation study for a resource-constrained project scheduling problem with multiple alternatives. We decide on a set of baseline schedules at the project planning phase, resulting in options to switch between execution modes of activities during project execution. We assess the performance of the set of baseline schedules under general mode implementation disruptions. A simple, yet effective algorithm is presented to construct the set of baseline schedules. Moreover, a general disruption system is proposed to model different disruption types, disruption dependencies and disruption sizes.     

RFID-enabled track and traceability in job-shop scheduling environment

This study presents an RFID-based traceability approach to improve production scheduling. An in-depth study for a manufacturer is conducted to explore scheduling options enabled by an RFID-based traceability system. We propose a novel information visibility-based scheduling (VBS) rule that utilizes information generated from the real-time traceability systems for tracking work in processes (WIPs), parts and components, and raw materials to adjust production schedules. We then evaluate the performance of this information visibility-based schedule against the classical scheduling rules. The results of the simulation suggest that an RFID-based scheduling rule generates better performance compared to traditional scheduling rules with regard to cycle time, machine utilizations, backlogs, and penalty costs. We also observe that the value of this information visibility is more relevant when the demand varies widely and/or operational disruptions occur.     

Scheduling start time dependent jobs to minimize the total weighted completion time

This paper deals with a single machine scheduling problem with start time dependent job processing times. The job processing times are characterized by decreasing linear functions dependent on their start times. The problem is to find a schedule for which the total weighted completion time is minimized. It is proved that the problem is NP-hard. Some properties of special cases of the general problem are also given. Based on these results, two heuristic algorithms are constructed and their performance is compared.     

Sequencing with uncertain numerical data for makespan minimisation

We consider a scheduling problem with the objective of minimising the makespan under uncertain numerical input data (for example, the processing time of an operation, the job release time and due date) and fixed structural input data (for example the precedence and capacity constraints). We assume that at (before) the scheduling stage the structural input data are known and fixed but all we know about the numerical input data are their upper and lower bounds, where the uncertain numerical data become realised at the control stage as the scheduled process evolves. After improving the mixed graph model, we present an approach for dealing with our scheduling problem under uncertain numerical data based on a stability analysis of an optimal makespan schedule. In particular, we investigate the candidate set of the critical paths in a circuit-free digraph, characterise a minimal set of the optimal schedules, and develop an optimal and a heuristic algorithm. We also report computational results for randomly generated as well as well-known test problems.