قابلیت برنامه ریزی واکنش پذیر تاخیر تجمعی برای تولید کارگاهی همراه با از هم گسیختگی دستگاه

This paper proposes a new when-to-schedule policy in reactive scheduling, which considers timing of schedule revision based on the concept of a control limit policy. Under the proposed policy, schedule revision is carried out based on a cumulative task delay which can be a measure to determine suitable timing of schedule revision. Some computational experiments demonstrate the effectiveness of the proposed policy by applying it to job shop problems with machine breakdowns, where we minimize maximum tardiness as well as scheduling frequency. It is also shown that the proposed policy with even low scheduling frequency can outperform an event-driven rescheduling approach, which is one of the major effective reactive scheduling methods.

Generating efficient schedules have widely been recognized as important in manufacturing. The general shop scheduling problems (Pinedo, 2002), are concerned with finding optimal/suboptimal schedules under some constraints. However, even relatively simple models such as a single-machine model cannot cope with them since they belong to the NP-hard class. In classical scheduling approaches, various methods for solving them efficiently have been developed (Morton and Pentico, 1993 and Pinedo, 2002), but most of them assume no variability of schedule attributes, the processing time of each individual job on each machine is assumed to be constant and a priori known. In real circumstances, however, large and complex manufacturing systems undergo delays of various jobs/tasks due to machine breakdowns, urgent jobs and other unexpected events. Accumulation of these delays will significantly disturb the smooth progress of the whole schedule and may result in low productivity of the manufacturing system. In practice, it is useful to regenerate the whole schedule (this is called rescheduling), revise the existing schedule, or let the system gradually absorb the delay, e.g., by right-shift operations at some points in time where the system shows changes of its state. These activities are generically called online scheduling. One of the important factors in building online scheduling models is how well they can manage uncertainties in the manufacturing environment. A number of studies addressing this kind of problems seem to have taken one of three approaches: One is to adopt a priority rule when a facility becomes free in order to select the next job to be processed. Another is to conduct rescheduling periodically and implement the yielding schedule to the facilities. The other is to revise a current schedule whenever an unexpected event altering system status occurs. In the first approach, the easy methods to be implemented are dispatching rules, which have been proposed over the last four decades (Blackstone, Phillips, & Hogg, 1982). In practice, the framework of simulation-based scheduling is widely used to find out appropriate dispatching rules among several candidates. However, restrictions of scheduling information occasionally force their rules to be myopic, and therefore dispatching rules cannot necessarily guarantee that the system holds its good performance level over a long time horizon (Church & Uzsoy, 1992). The second approach on a rolling horizon basis solves a multi-period scheduling problem at previously planned time points and implements only the first period’s schedule (Baker & Peterson, 1979). The disadvantage of this approach is that the planned (re)scheduling interval may cause a serious compromise of the system performance due to unforeseeable but significant changes in the system state. This indicates an adequate scheduling interval should be determined in the planning phase. The last approach, which we refer to as a reactive scheduling, aims to cope with unexpected events by revising the existing schedule after these events. Most studies have addressed a how-to-schedule policy, which discuss a method of schedule revision, by means of knowledge-based technology ( Kerr and Szelke, 1995, Noronha and Sarma, 1991 and Smith, 1995) on the basis of an event-driven approach. The terminology “event” is used here to mean a factor of uncertainties which may delay the progress of a schedule, such as machine breakdowns, dynamic job arrivals, job cancellations, delays in material arrivals, under- or overestimation of processing times. In this approach, substantial events altering the system status over time are supposed to be classified into (i) critical ones requiring prompt reaction and (ii) those which can be ignored for the moment because every event does not cause an immediate schedule change ( Church & Uzsoy, 1992). There is, however, no generic model or method for such event classification. This implies that a typical event-driven approach reacting to contingency directly has the disadvantage that it strongly depends on shop-floor circumstances. As far as it can be investigated, only a few studies have addressed building a generalized decision model focusing on when-to-schedule policy which determines schedule decision points in time. From the above point of view, this study proposes a new when-to-schedule policy in reactive scheduling which will be capable of building a generalized model to determine the time to schedule. Under the proposed policy, we inspect a current schedule to detect its delays at planned times and make a judgment whether or not we should conduct schedule revision at each individual planned inspection time on the basis of the cumulative size of delays. This concept is from that of a control limit policy ( Derman, 1966). We first define a delayed task and a cumulative task delay, which can be viewed as aggregated information of unexpected events. Second, we describe job shop scheduling problems to which our reactive schedule revision approach is applied, and then clarify some properties of cumulative task delays. The applicability of delay-based measurement is also investigated. In addition, tabu search ( Adenso-Diaz, 1992, Morton and Pentico, 1993 and Pinedo, 2002) is used to generate a predictive schedule and carry out reactive schedule revision (how-to-schedule policy). Some computational experiments demonstrate the effectiveness of the proposed policy by applying it to job shop problems with machine breakdowns, where we minimize the maximum tardiness. To evaluate the proposed policy, we introduce minimizing scheduling frequency as well since frequent scheduling does not necessarily improve the situation with much expense for its operations and, instead, makes the system behavior hard to predict, which will reduce the effectiveness of upper level planning systems. We also compare the proposed policy with a typical event-driven approach to show that cumulative task delay can be a schedule decision measure in reactive scheduling.

In the actual shop floors, the process of jobs often undergoes delays because of uncertainties, most of which are not foreseen at the planning phase. We have proposed a new when-to-schedule policy in reactive scheduling under job shop environment, where we conduct periodical inspection to the schedule to detect task delays and carry out schedule revision if cumulative task delay exceeds a prespecified value called the critical cumulative delay. Under such a policy, the timing of inspection and the critical cumulative delay are design variables. We first showed through computational experiments that a cumulative task delay tends to increase remarkably and rapidly with elapsed time of the schedule. We then investigated the applicability and the effectiveness of the proposed policy by comparing it with an event-driven rescheduling policy. It was shown that when we emphasize the maximum tardiness of the schedule as well as the schedule revision frequency, the proposed policy tends to outperform the event-driven rescheduling approach. The proposed policy should be extended to job shop scheduling with resource constraints, flexible manufacturing systems, and other types of scheduling, which can be considered more practical but complicated. The future work also should deal with an analytical model to determine the values of parameter D∗D∗ considering the practical use of the proposed policy.