Abstract
We conjecture that when the uncertainty of scheduling information increases, one should change from deterministic, through robust to, finally, online scheduling techniques. Previously, extensive mathematical investigations have been carried out on the stability of a deterministic schedule for uncertain operation processing times. In this paper, we will use an empirical approach and an entropy measure to justify the transition between deterministic, robust and online scheduling. The use of an entropy measure in our context can be perceived, in a broader sense, as a pro-active approach to deal with changes in the level of information uncertainty and relative importance of each term in the total schedule execution cost. The level of information uncertainty may change due to the performance deterioration of processors (machines or human) and the replacement of old machines with new ones; and the changes in relative importance of cost elements may be due to changes in shop floor priorities and pressure from partners in the supply chain network. One can decide upon the scheduling strategies to be employed based on the latest entropy value of the information considered and the relative importance of each cost term.
Notes
A crossover value is the value of (H p /n) for which a change in dominance of scheduling technique occur. For example, in , (H p /n) = 1.7 is a crossover value for ψ = 0 and ν = 0.2, since for values <1.7, deterministic technique dominates and for values >1.7, online technique dominates.
Dominance transition patterns are transition patterns observed in the neighbourhood of a crossover point. For example, and show similar transition pattern in the neighbourhood of (H p /n) = 1.7, since the dominant technique changes from deterministic to online for ψ = 0 and ν = 0.2 and the dominance behaviour for other combinations of cost coefficients remains unchanged.
Recall that an online scheduling technique commits operations over time. Each time an operation is committed, the unscheduled list of operations has to be sorted again, since there may be changes in processing time. The sorting algorithm, which runs in O(n log n) time, will be used n times.
These rankings are obtained by observation of the results obtained from other experiments carried out by the authors. Details of these experiments have been omitted from this paper due to their length.