Hybrid Robust Scheduling For Single Machine Subject To Random Breakdown

In the operational management, rational planning and saving production costs have become a core issue to enhance enterprise competitiveness. Moreover, the key to them is to obtain an optimal scheduling scheme. Production scheduling problem is a class of complex combinatorial optimization problems, where most of them have been proved to be NP-hard, and incorporating the uncertainties exsiting in the execution environment of scheduling problems may decrease the gap between scheduling theory and industrial practice. Therefore, the efforts concentrating on production scheduling have not only significant academic value but also great practical meaning.Single machine scheduling problem is the most basic form of scheduling problem, where a set of jobs is to be scheduled on a single machine. However, single machine models are important for various reasons. The single machine environment is very simple and a special case of all other environments. Single machine models often have properties that neither machines in parallel nor machines in series have. The results that can be obtained for single machine models not only provide insights into the single machine environment, but also provide a basis for heuristics that are applicable to more complicated machine environments. In fact, scheduling problems in more complicated machine environments are often decomposed into subproblems that deal with single machine.The nature of dynamic characteristics in real-life manufacturing environments makes the scheduling problems under uncertainties (also known as dynamic scheduling) more complex. Schedule robustness is the major measure concerned by dynamic scheduling. Hence, robust scheduling problems have been the research focus of the scheduling field. However, the research efforts in the robust scheduling problems are mainly based on either proactive scheduling or reactive scheduling, and the literature on hybrid robust scheduling is rather sparse. Therefore, this paper proposed the general framework of hybrid robust scheduling, and hybrid robust scheduling methods under random breakdown was investigated in detail with single machine model of scheduling as research platform. To exam the effectiveness of hybrid robust scheduling methods, the main efforts are as follows.A hybrid robust scheduling with stability as criterion for single machine with random breakdown is dealt with. The single machine scheduling problem is subject to random machine breakdown, where jobs arrive at system dynamically. A modified version of Optimized Surrogate Measure Heuristic (OSMH) developed by Mehta and Uzsoy (1999) is proposed, i.e., Modified Optimized Surrogate Measure Heuristic (MOSMH). The idea behind the heuristic MOSMH is to make full use of the idle times probably existing in initial schedule. The stability of the predictive schedule is measured by the sum of the weighted absolute deviation between the planned job completion times and the realized one. Extensive computational results show that the heuristic MOSMH proposed in this paper significantly improves the schedule stability without deteriorating the efficiency performance and the predictive schedule obtained by MOSMH is more insensitive to the various breakdown scenarios than the heuristic OSMH, which fully demonstrates the effectiveness of the hybrid robust scheduling, proposed in this paper, for single machine with random breakdown.A hybrid robust scheduling with bi-objective as criterion for single machine subject to random breakdown is considered. The research effort is to find predictive schedule with performance robustness (referred to as robustness) and sulotion robustness (known as stability) for a single machine subject to random machine breakdown, where jobs arrive dynamically and the total weighted tardiness is the performance to be optimized. The problem is a bi-objective optimization. To generate the predictive schedule, the obustness and stability are considered simultaneously. Two surrogate measures for robustness and stability are developed and embedded in a simulated annealing algorithm to obtain the predictive schedule. Then the predictive schedule is released into shop floor to be executed. On occurrence of a machine breakdown, the right shifting rescheduling (RSR) is used to accommodate the breakdown. The test problems are carried out to exam the surrogate measures. The extensive computational results show that the schedule generated by our method can provide better robustness and stability and it is more insensitive to the various breakdown scenarios, which shows a good effecitiveness of the hybrid robust scheduling, presented in this paper, for single machine with random breakdown.