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

The traditional focus of scheduling research is on finding schedules with a low implementation cost. However, in many real world scheduling applications finding a robust or flexible schedule is just as important. A robust schedule is a quality schedule expected to still be acceptable if something unforeseen happens, while a flexible schedule is a quality schedule expected to be easy to change. In this paper, the robustness and flexibility of schedules produced by minimising different robustness measures are investigated. One kind of robustness measure is the neighbourhood-based robustness measure, in which the basic idea is to minimise the implementation costs of a set of schedules located around a centre schedule. For tardiness problems another way of improving robustness is to increase the slack of the schedule by minimising lateness instead of tardiness. The problems used in the experiments are maximum tardiness, summed tardiness and total flow-time job shop problems. The experiments showed that the neighbourhood-based robustness measures improves robustness for all the problem types. Flexibility is improved for maximum tardiness and loose summed tardiness problems, while it is not improved for tight summed tardiness problems and total flow-time problems. The lateness-based robustness measures are found to also improve robustness and in some cases flexibility for the same problems, but the improvement is not as substantial as with the neighbourhood-based measures. Based on these observations, it is conjectured that neighbourhood-based robustness can be expected to improve flexibility on problems with few critical points.

When solving a scheduling problem the focus traditionally is on minimising a measure of the cost of implementing the schedule. However, most real world scheduling systems operate in dynamic environments, in which unforeseen and unplanned events can happen at short notice. Such events include the breakdown of machines, employees getting sick, new jobs appearing, etc. The problem encountered when an unforeseen event and a schedule has to be changed is usually called a rescheduling problem. When a rescheduling problem is solved a new schedule incorporating the changes in the environment and the part of the preschedule (the schedule followed prior to the breakdown) already implemented is sought. This schedule should ideally have as low an implementation cost as possible. When the unforeseen event is a breakdown (the temporary unavailability of a resource), the simplest way to solve a rescheduling problem is often to keep the processing order of the preschedule, but delay processing when necessary. In the following this kind of rescheduling is called simple rescheduling or right-shifting. Right-shifting is the simplest and fastest kind of rescheduling, but in order to improve performance more complex methods searching some set of schedules can be used. In the following, this is called rescheduling using search. The difficulty of the rescheduling problem depends on the nature of the breakdown as well as the preschedule. Some preschedules will generally lead to rescheduling problems with lower implementation costs than others. A preschedule which tends to perform better than ordinary schedules after a breakdown and right-shifting is termed robust, while a schedule which tends to perform well after a breakdown and rescheduling using search is termed flexible. It is difficult to relate the terms flexibility and robustness to each other. Often a schedule which is robust can also turn out to be flexible to some degree, since robustness means that the schedule is still acceptable if small delays happen during schedule execution. The acceptability of small delays is an advantage if small changes are made to the schedule. On the other hand, the acceptability of small delays does not necessarily say anything about the possibility of making profound changes in the schedule. The objective of this paper is to investigate two ways of achieving schedule robustness and flexibility for job shop problems. The first way is the neighbourhood-based robustness measure technique used in [10] on makespan problems, which is reformulated for maximum and summed tardiness, and total flowtime problems. The second way is a simpler idea applicable to tardiness problems; by minimising a measure of lateness instead of tardiness, the slack in the schedules can be increased, which may improve the rescheduling performance of the schedules. The slack of an operation in a schedule is the “buffer time” by which the operation can be delayed without worsening the performance of the schedule. The work presented in this paper is an extension of the work presented in [11], in which the neighbourhood-based robustness idea was compared to ordinary scheduling for the performance measures maximum tardiness, summed tardiness and total flow time on a smaller range of problems. The outline of the paper is as follows. Section 2 defines the job shop scheduling problem and notation. In Section 3 previous work on robust scheduling is briefly covered. Section 4 introduces the robustness measures for the maximum, summed tardiness and total flow-time job shop problems. In Section 5 the genetic algorithm used to perform the scheduling is described, while Section 6 describes how breakdowns are simulated and how rescheduling is performed in the experiments. Section 7 describes the experiments and reports the results. Section 8 contains the conclusions.

In this paper, the robustness and flexibility of tardiness and total flow-time job shop schedules facing breakdowns have been investigated. The schedules have been produced with a GA optimising standard performance (cost), neighbourhood-based robustness measures and lateness robustness measures (for the tardiness problems). The lateness-based robustness measures have been demonstrated to improve schedule robustness and flexibility for loose maximum tardiness and loose summed tardiness problems, while they have been found equivalent to standard scheduling on tight problems. It has been demonstrated that the neighbourhood-based robustness measures generally seem to improve schedule robustness for all problem performance measures tried, and both for tight and loose tardiness problems. Schedule flexibility in many cases seems to be improved for maximum tardiness problems and loose summed tardiness problems, while it does not seem to be improved for tight summed tardiness problems and total flow-time problems, in which case the flexibility is sometimes seen to be worse than for standard scheduling. For many problems, the improvement in robustness and flexibility when using the neighbourhood-based robustness measures were found to be better than the improvement gained from using the lateness-based robustness measures. The explanation of the poor flexibility of the schedules produced using neighbourhood-based robustness measures for total flow time and for the deteriorating flexibility of the summed tardiness schedules as the problems become more tight may be that when flexibility is sought, the neighbourhood-based robustness idea works best for problems in which there are few critical points. A critical point is a part of the schedule which cannot be changed without worsening the schedule. In makespan problems or maximum tardiness problems this will often be the case. There will usually be one job which is the “worst”. The other jobs can be sacrificed in order to alleviate problems (breakdowns) worsening this one job. For loose summed tardiness problems there will often only be one or a few critical jobs as well (if there are only few tardy jobs). As the problems become more tight the situation becomes more diffuse. There is no longer one critical job, but a number of them making the rescheduling problem more complex. The higher complexity of the rescheduling problem may result in a low implementation cost of the preschedule becoming more important for rescheduling performance than anything else, and decreasing the probability finding a good solution to the rescheduling problem close to the preschedule. These observations are valuable if neighbourhood-based robustness is to be applied to real world scheduling problems or other combinatorial optimisation problems, since it gives the person working with the problem a hint as to whether neighbourhood-based robustness measures will work or not.