On deterministic online scheduling: Major considerations,paradoxes and remedies

Despite research in the area, the relationship between the (open-loop) optimization problem and the quality of the (closed-loop) implemented schedule is poorly understood. Accordingly, we first show that open-loop and closed-loop scheduling are two different problems, even in the deterministic case. Thereafter, we investigate attributes of the open-loop problem and the rescheduling algorithm that affect closed-loop schedule quality. We find that it is important to reschedule periodically even when there are no “trigger” events. We show that solving the open-loop problem suboptimally does not lead to poor closed-loop solutions; instead, suboptimal solutions are corrected through feedback. We also observe that there exist thresholds for rescheduling frequency and moving horizon length, operating outside of which leads to substantial performance deterioration. Fourth, we show that the design attributes work in conjunction, hence, studying them simultaneously is important. Finally, we explore objective function modifications and constraint addition as methods to improve performance.     

Greedy randomized adaptive search for dynamic flexible job-shop scheduling

Dynamic flexible job shop scheduling problem is studied under the events such as new order arrivals, changes in due dates, machine breakdowns, order cancellations, and appearance of urgent orders. This paper presents a constructive algorithm which can solve FJSP and DFJSP with machine capacity constraints and sequence-dependent setup times, and employs greedy randomized adaptive search procedure (GRASP). Besides, Order Review Release (ORR) mechanism and order acceptance/rejection decisions are also incorporated into the proposed method in order to adjust capacity execution considering customer due date requirements. The lexicographic method is utilized to assess the objectives: schedule instability, makespan, mean tardiness and mean flow time. A group of experiments is also carried out in order to verify the suitability of the GRASP in solving the flexible job shop scheduling problem. Benchmark problems are formed for different problem scales with dynamic events. The event-driven rescheduling strategy is also compared with periodical rescheduling strategy. Results of the extensive computational experiment presents that proposed approach is very effective and can provide reasonable schedules under event-driven and periodic scheduling scenarios.     

From volunteer to trustable computing: Providing QoS-aware scheduling mechanisms for multi-grid computing environments

The exploitation of service oriented technologies, such as Grid computing, is being boosted by the current service oriented economy trend, leading to a growing need of Quality of Service (QoS) mechanisms. However, Grid computing was created to provide vast amounts of computational power but in a best effort way. Providing QoS guarantees is therefore a very difficult and complex task due to the distributed and heterogeneous nature of their resources, specially the volunteer computing resources (e.g., desktop resources).The scope of this paper is to empower an integrated multi QoS support suitable for Grid Computing environments made of either dedicated and volunteer resources, even taking advantage of that fact. The QoS is provided through SLAs by exploiting different available scheduling mechanisms in a coordinated way, and applying appropriate resource usage optimization techniques. It is based on the differentiated use of reservations and scheduling in advance techniques, enhanced with the integration of rescheduling techniques that improve the allocation decisions already made, achieving a higher resource utilization and still ensuring the agreed QoS. As a result, our proposal enhances best-effort Grid environments by providing QoS aware scheduling capabilities.This proposal has been validated by means of a set of experiments performed in a real Grid testbed. Results show how the proposed framework effectively harnesses the specific capabilities of the underlying resources to provide every user with the desired QoS level, while, at the same time, optimizing the resources’ usage.     

Searching for close alternative plans

Consider the situation where an intelligent agent accepts as input a complete plan, i.e., a sequence of states (or operators) that should be followed in order to achieve a goal. For some reason, the given plan cannot be implemented by the agent, who then goes about trying to find an alternative plan that is as close as possible to the original. To achieve this, a search algorithm that will find similar alternative plans is required, as well as some sort of comparison function that will determine which alternative plan is closest to the original. In this paper, we define a number of distance metrics between plans, and characterize these functions and their respective attributes and advantages. We then develop a general algorithm based on best-first search that helps an agent efficiently find the most suitable alternative plan. We also propose a number of heuristics for the cost function of this best-first search algorithm. To explore the generality of our idea, we provide three different problem domains where our approach is applicable: physical roadmap path finding, the blocks world, and task scheduling. Experimental results on these various domains support the efficiency of our algorithm for finding close alternative plans. A preliminary version of this paper appeared in the International Joint Conference on Autonomous Agents and Multiagent Systems (8). An erratum to this article can be found at     

Filtered-beam-search-based algorithm for dynamic rescheduling in FMS

In the practical production process of a flexible manufacturing system (FMS), unexpected disturbances such as rush orders arrival and machine breakdown may inevitably render the existing schedule infeasible. This makes dynamic rescheduling necessary to respond to the disturbances and to improve the efficiency of the disturbed FMS. Compared with the static scheduling, the dynamic rescheduling relies on more effective and robust search approaches for its critical requirement of real-time optimal response. In this paper, a filtered-beam-search (FBS) -based heuristic algorithm is proposed to solve the dynamic rescheduling problem in a large and complicated job shop FMS environment with realistic disturbances. To enhance its performance, the proposed algorithm makes improvement in the local/global evaluation functions and the generation procedure of branches. With respect to a due date-based objective (weighted quadratic tardiness), computational experiments are studied to evaluate the performance of the proposed algorithm in comparison with those of other popular methods. The results show that the proposed FBS-based algorithm performs very well for dynamic rescheduling in terms of computational efficiency and solution quality.     

Coordination and Task Interdependence during Schedule Adaptation

This article discusses the influence of organizational and behavioral variables on coordination between planners during plan adaptation. Fast communication and mutual alignment are necessary to maintain schedule feasibility in a situation with several schedulers. Therefore, coordination modes are required that facilitate communication and joint problem solving. Moreover, building on interdependence theory, we hypothesize that the schedulers' perceptions of task interdependence influence rescheduling performance. Experimental results indicate that a group decision‐making coordination mode enforcing cooperation outperforms a distributed decision‐making coordination mode involving emergent alignment. The level of perceived task interdependence explains this better performance. Therefore, perceptions of task interdependence are put forward as an important behavioral factor influencing rescheduling performance, with several important implications for theory and practice. © 2011 Wiley Periodicals, Inc.     

就绪时间受限的负荷单机环境下返工工件重调度方法

研究了返工工件的单机重调度问题.在初始调度中初始工件带有不同的就绪时间,优化目标为最小化初始工件等待时间和;重调度时在满足每个初始工件最大等待时间约束情况下安排返工工件的生产,优化目标为最小化所有工件等待时间和.文中首先建立了RRSM （Rescheduling for reworks on single machine）问题模型,并证明其为NP难问题.然后,提出并证明了三个RRSM问题性质,进而根据诸性质设计了求解RRSM问题的动态插入启发式（Dynamic insert heuristic,DIH）算法.证明了应用DIH算法能在多项式时间内求得两种特殊RRSM问题的最优解. 最后,分析了DIH算法解的特点,给出了最优解的判定方法,并通过算例说明了DIH算法的有效性.     

Real-time GA-based rescheduling approach for the pre-sewing stage of an apparel manufacturing process

In this paper, a real-time segmentation rescheduling (RSR) approach using genetic algorithms to handle the production planning and scheduling problem in dynamic apparel manufacturing environment is proposed. Experiments based on the actual production data were conducted to validate the performance of the RSR approach. The experimental results indicated that the makespan and the influence caused by the change of schedule could be minimised.     

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.     

Deadlock-free Rescheduling in Flexible Manufacturing Systems

The dynamic nature of manufacturing makes rescheduling essential in today's complex production environment, particularly in flexible and re-configurable systems. Research on optimizing schedules, that includes deadlock avoidance, is rather limited. Furthermore, the deadlock problem is mostly ignored in research on rescheduling. A rescheduling algorithm, that uses time Petri-Nets and the minimal siphons concept, was developed to deal with sources of disturbance such as machine breakdowns in real-time. It guarantees a deadlock-free new schedule. The existence of alternative routes, availability of material handling facilities, and the limitation of buffer capacities were taken into consideration. The developed algorithm modifies only the affected portion of the original schedule, rather than rescheduling all jobs, in order to limit changes to the original schedule and reduce the impact on the response time.