## 4 Algorithms for Core System Functionality  
### Dispatching Level Heuristics  
The heuristics chosen for the dispatching level are PDRs. Due to their approximate nature, they seldom find the optimum solution. However, this has not posed a significant disincentive regarding their practical implementation. Ever since their initial conception through the Giffler-Thompson algorithm [19], PDRs have been used extensively in actual manufacturing environments due in large to the alignment of their mathematical formulation with the shop floor [20]. For example, a worker is capable of easily understanding the concepts of SPT, earliest due date (EDD), and first in first out (FIFO), while those of ant colony optimization and artificial immune system are harder to grasp. Another reason for their wide practical use is their speed in producing schedules: Where a branch and bound technique or a mixed-integer linear programming (MILP) model would have to run for a very large amount of time, PDRs produce schedules in a matter of seconds. This is of huge importance in real industrial situations such as the one highlighted in this paper since unexpected events, such as machine breakdown and rush orders, may, and more often than not, do happen. A new schedule must be constructed on the fly so time-consuming algorithms are avoided. From a problem-solving perspective and for the efficient application of PDRs, it was deemed preferable to break down the original \(n\times m\) problem, where n represents the production orders and m represents the machines, into a series of single-machine \(n\times 1\) instances with a common due date, solve them one by one, and then aggregate the partial  
Figure 3: The G-DSS’s framework. sequences to construct a full schedule. Precedence constraints between orders are ignored at this stage. The reason for such a decomposition strategy was twofold: Firstly, the order backlog created by the MRP function discretely assigns SKUs to work centers and BOM effectivity dates, and secondly, the large number of orders traversing the shop floor significantly increases problem complexity when concurrently catering for the BOM tree structure. Empirical analysis showed that schedule quality does not considerably improve by solving the constrained \(n\times m\) problem, while the computational overhead can be up to 150 times as much. For example, when scheduling the cutting group whose typical problem size can be 201 \(\times\) 10, aggregation of the \(n\times 1\) partial schedules takes, on average, 6s on a low-end 3.10 GHz dual-core system with only 4096 MBs of RAM. In contrast, using a genetic algorithm approach, the/problem took a minimum of 15 min on the same hardware platform. The approach taken was further validated by the production staff that preferred rapid scheduling and rescheduling over close to optimal schedules. Table 4 shows how the 201 \(\times\) 10 instance is broken down into 10 \(n\times 1\) problems. It should be noted that in the relevant table, the two production planning periods (PPPs) are chosen randomly. For these two, the active SKUs (according to BOM effectivity dates) are presented, along with the total SKU number (all BOM trees). Columns 4 and 5 depict the production order number without and with late order inclusion. As can be seen, late orders are numerous and significantly overburden scheduling. The main reason for such a large number is the poor performance of the PPC tool, the extensive outsourcing (subcontractors violate due dates), and a sizeable amount of orders with small quantities (two to three components) that accumulate over the year. Another point of interest is the fluctuating number of active SKUs. For the selected PPPs, none of the active SKUs were bound to work centers A654 and A653. If late orders are included, seven new production orders are allocated to those centers, which evince that BOM effectivity dates may overlap, thus further contributing to problem complexity.