Make your own free website on Tripod.com

Study of effect of decision delay on Makespan



Environment


In any job shop, decisions need to be taken regarding routing of jobs. Typically a job can be processed on one of a set of capable machines. The decision maker needs to select a suitable machine from this pool.
Since the decision on how to route the job requires some computation, the in-transit waiting time of the job increases. These experiments serve to study the effect of a delay during this decision making process on the shop objective,in this case to minimize makespan.

Three commonly used rules for routing logics on the shop floor are:
  1. Minimum Queue Length Rule. According to this rule, amongst the set of machines capable of processing a job, the machine with the minimum number of pending jobs is allotted the job.
  2. Minimum Processing Work Rule. According to this rule, amongst the set of machines capable of processing a job, the machine with the least remaining work to be completed is assigned the job.
  3. Minimum Total Work Rule. According to this rule, amongst the set of machines capable of processing a job, the machine with the least remaining total work is assigned the job. Total work is different from processing work remaining in that it considers the number of setup changes required and time spent in setup changes. Note also the correspondence of the machine sequencing logic (LPT, SPT, FCFS) with the number of setup changes.

Due to the complexity of the computation, and assuming that all relevant data is readily available, the minimum Total Work rule entails the largest delay relative to other rules. Thus, in order to capture this difference, the effect of an equivalent delay using the two other rules was noted.

Equivalent delay for the minimum Q length rule was taken as one-fourth of the delay for the total work rule. Equivalent delay for the minimum processing work rule was taken as half of the delay for the total work rule.

Effect of adjusted decision delay on makespan


Analysis

In this shop, all machines employ LPT sequencing logic. Earlier experiments have shown this common sequencing logic, across the shop, effectively minimizes makespan.

The graph (Figure 1) suggests that
Unadjusted effect of decision delays

As seen in Figure 2, the minimum total work rule is only marginally better than the minimum Q length rule or the minimum processing work rule in reducing makespan.
Possible reasons could be:

Waiting Time distribution



Use of Genetic Algorithms for Routing


The previous experiment showed that owing to the very little waiting time experienced by jobs, the three routing rules yield similar results. In applying these rules to the shop, the sequencing logic on each machine was kept the same throughout the simulation. However, research in Job Shop Scheduling has led to heuristics like the shifting bottleneck procedure, which suggest that sequencing logic on machines should be dynamically changed in accordance with load.

In order to carefully sift through such changing sequencing rules at each machine, the sequencing logic is abstracted to deal with prioritized operations. Thus,the sequencing logic is to schedule higher priority operations first. In order to improve on the system objective, for example, makespan, the operation priorities may be adjusted as needed.

As an example, for reducing makespan, the operation priorities could be adjusted such that:

Comparison of GA to Shop routing rule

Analysis


The GA implementation is seen to consistently outperform the minimize total work rule applied to a shop with all machines on LPT logic. These results from GAs were obtained through random generation of operation priorities alone. Using the above techniques for modifying the GA solution (mutation) for a particular objective, good schedules can be generated rapidly.

Note however that the performance of the GA also degenerates rapidly with increasing decision delay. Note that for a clearer picture, the above graph should be seen using equivalent decision delays. For example a delay of 5 minutes for the GA model may correspond to only 3 minutes for the Total work rule (owing to computational complexity).
For the GA implementation, the decision delay corresponds to the decision taker running the GA model for an efficient schedule based on the current shop conditions. This is an approximation.

As discussed above, the degeneracy in the performance can be attributed to the small waiting times experienced by over 90% of the operations (< 1 minute). Thus, adding a decision delay of anything above 1 minute affects makespan directly.