-
Notifications
You must be signed in to change notification settings - Fork 1
HeuristicsDescription
Description of the Dispatching Rules Included in the Study.
-
Tie-Breaker: This rule schedules jobs in non-decreasing order of their job number, assigned to jobs at the point of their arrival by a counter. It is a very simple rule that ensures a deterministic order as two jobs can never have the same number. It is therefore also used in combination with all the other rules below to break ties between jobs having the same priority according to the primary rule.
-
SPT: The Shortest Processing Time (SPT) rule, which schedules jobs in non-decreasing order of the processing time of their imminent operations, originates from
- W. E. Smith
- Various optimizers for single-stage production
- Naval Research Logistics Quarterly 3(1–2), 1956, pp. 59–66
The SPT rule yields the minimum mean flow time for the static single machine problem and is therefore commonly used as a benchmark for other scheduling problems with the mean flow time objective.
- PT+WINQ: The Processing Time plus Work In Next Queue (PT+WINQ) rule has been specifically designed for dynamic job shop problems such as those examined in this study, and has been developed in
- O. Holthaus and C. Rajendran
- Efficient dispatching rules for scheduling in a job shop
- International Journal of Production Economics 48(1), 1997, pp. 87–105
The PT+WINQ rule aims to trade off the minimisation of the local mean flow time with the importance of balancing the queue lengths (in terms of processing time) of other machines to avoid idle times due to starvation.
- 2PT+WINQ+NPT: This rule is an extension of the PT+WINQ rule, developed in
- O. Holthaus and C. Rajendran
- Efficient jobshop dispatching rules: further developments
- Production Planning & Control 11(2), 2000, pp. 171–178
The main difference is the incorporation of the processing time of the subsequent operation of a job so that short jobs can be quickly pushed through their next two operations. In the above paper, the 2PT+WINQ+NPT rule is shown to be the more effective rule than SPT and PT+WINQ for the minimisation of mean flow time in dynamic job shops.
- IFT−UIT+NPT: This rule has resulted from a study of the limitations of the PT+WINQ rule, published in
- J. Branke and C. W. Pickardt
- Evolutionary search for difficult problem instances to support the design of job shop dispatching rules
- European Journal of Operational Research 212(1), 2011, pp. 22–32
Specifically, it is based on the observations that the minimisation of the local mean flow time should take into account all waiting jobs, that the future (rather than the current) queue lengths should be assessed, and that the focus should be more on idle time avoidance than the balancing queue lengths.
- GECCO2010-genSeed-2reps, GECCO2010-genSeed-10reps: These two rules have been generated specifically for the dynamic job shop problems examined in this study by means of a Genetic Programming (GP) hyper-heuristic, described in
The paper also provides a detailed description of the latter rule.
- ASP2013-Rule #6: This rule has been generated for dynamic job shop problems similar to those examined in this study by means of a Multi-Objective GP (MOGP) hyper-heuristic, proposed in
The ASP2013-Rule #6, which is also described in detail in the above paper, is shown to be the best rule in that study for the minimisation of mean flow time. However, the rule can be still considered a comprise rule since the hyper-heuristic is configured to design rules for multiple objectives.
- EC2014-LIN_BASE-Rule: This rule has the same basic priority function as the 2PT+WINQ+NPT rule, where the coefficients within that function have been optimised by a Covariance Matrix Adaptation Evolution Strategy (CMA-ES) hyper-heuristic, as described in
Due to its simple priority function, the EC2014-LIN_BASE-Rule can be easily understood by a human user, despite having been generated by a hyper-heuristic.
- EC2014-TREE_BASE_NORM_ND-Rule, EC2014-TREE_EXT_NORM_ND-Rule: These two rules have been specifically generated for some of the dynamic job shop problems examined in this study by means of a GP hyper-heuristic, which is provided with normalised attributes and equipped with a duplicate eliminiation procedure (see also the above paper).