# 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.

## 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
• The makespan is highly sensitive to decision delays.
• The minimum total work rule fails dramatically when compared to an equivalent minimum Queue Length rule. The equivalent rules are justified in a shop where routing decisions are manually taken.
• For a delay less than 2 minutes, both minimum processing rule and minimum Q Length rule yield similar performance.

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:
• Higher sensitivity of Total Work rule calculation to jobs added in future to the machine. For example, if a job P is added to machine after job J is assigned after calculations- owing to perhaps P having longer processing time, it is processed before J, thus changing the computation regarding number of setup changes and expected job completion time. An experiment to test this hypothesis would track the actual completion time of an operation, versus the value calculated during routing decision for total work rule. (TODO)
• Idle machines. If even one machine in the pool of capable machines is idle,by all three rules, it will receive the job. Thus, there would be no difference amongst the three rules. In turn it follows that, whenever machines with very small queues exist, they will invariably be assigned the job by all three rules. In order to test this hypothesis, one can look at the distribution of waiting times at each machine of all jobs in the shop. This is shown in Figure 3. As seen from the graph, out of 6000 operations, about 90 percent have waiting time less than a minute, and 60 percent have zero waiting time.Thus, most machines have zero or very small queues, and thus the different rules do not give very varied results.

# 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:
• Number of setups involved is reduced, which can be accomplished by giving similar priority to similar operations.
• Operations with large processing times do not incur large waiting times. This is in accordance with the LPT logic seen to give good performance for the minimize makespan shop objective.
• Operations with large remaining work do not incur large waiting times. If jobs with a number of incomplete operations incur large waiting times,then it will most likely increase the overall makespan.

## 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.