Study of effect of decision delay on Makespan
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:
- 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.
- 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.
- 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.
In this shop, all machines employ LPT sequencing logic. Earlier experiments
have shown this common sequencing logic, across the shop, effectively minimizes
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
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
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
- 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.
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