D e p a r t m e n t o f
The Scheduling and Evaluation Tool (SET)
Scheduling within SET
Evaluating the Effectiveness of Schedules
Results and Recommendations
Limitations and Extensions
About The Authors
Establishing efficient and effective scheduling procedures is essential for any manufacturing firm. The flexible packaging firm AEP Flexipac relies on quality scheduling of its extrusion, printing, laminating, slitting and conversion operations to ensure customers’ orders are completed on time and in full as customer service is of paramount importance. Other factors also need to be considered when scheduling, such as minimising down time caused by changeovers and the holding cost associated with storing work-in-progress and finished goods before delivery.
Although AEP Flexipac have software which is capable of automating most of their scheduling, the process has to date been judged too complex to model to sufficient detail, and they hence rely on in-house knowledge to perform these duties. Consequently, the main objective of the project was to produce a scheduling package which would allow analysis of different methods of scheduling. Such a tool also allows staff to gain insights into the efficiency of shop floor operations by comparing different possible schedules ahead of time.
Scheduling of orders on the various machines at AEP Flexipac is currently conducted manually. In the printing section alone, this requires around 600 orders a month to be placed into a suitable position in the schedule of one of the nine print machines. This process has proved to be very time-consuming, but until recently, the high complexity of the scheduling requirements have resulted in the automation of scheduling being ruled out. The software currently used to store the schedules, ‘The Planner’, is capable of producing rule-based schedules automatically, but appropriate scheduling rules have not as yet been documented.
Another issue is that staff at AEP Flexipac cannot predict the impact of changing schedules and machine capacity alterations on shop-floor operations. The effectiveness of schedules and machine utilisation is currently only determined after the fact.
The main aim of the project was to provide a prototype scheduling and evaluation package to improve the efficiency of scheduling of the print machines while maintaining the effectiveness of the schedules produced. The package offers a set of possible schedules which can be evaluated according to a set of performance measures. The performance measures also permit staff to predict the impact of changes in machine capacity and schedules on shop-floor operations. Furthermore, this project allowed some recommendations to be made as to whether resources should be used to automate scheduling in the current software available. The diagram below illustrates how SET can be incorporated into the current operations at AEP. Click on the following link for more detail about the Scheduling and Evaluation Tool.
The scheduling function of SET allows three different methods of scheduling; Tabu Search, rule-based scheduling, and manual changes.
Tabu Search is a search technique commonly used to find good schedules within production scheduling. Each iteration of the technique involves the evaluation of a set of possible 'moves', where a move in this instance can be a swap between two items in a schedule or the insertion of a particular item in a different position in the schedule. The moves are evaluated in terms of a chosen objective within SET, such as reducing the cost of late deliveries or the holding cost incurred. The swap or insertion that offers the lowest cost or penalty is utilised as the move for the iteration, and the schedule is updated accordingly. The next iteration explores swaps and insertions of the updated schedule.
When an item is involved in a move, it is added to the Tabu List which prevents it from being involved in further moves until enough orders are added to the list so that it can be removed. A utilised move may only involve items on the Tabu List if it generates a more effective schedule than those that have been previously found. The search is completed when a certain period of time has elapsed, as specified by the user. At this time, the best known schedule is stored as the final solution.
Currently the AEP Flexipac staff schedule print orders by informal rules based on experience. These rules, in tandem with examining effective schedules found from implementing Tabu Search, gave way to the rule-based scheduling available in SET. The rule-based scheduling sorts orders according to combinations of criteria. The main criteria considered were the due date of orders, latest completion time, ink type and family, where a family is defined as a group of items produced under the same brand name.
As it would be very difficult to model the full complexity of the scheduling requirements at AEP Flexipac, manual swaps and insertions can be made within SET if necessary. These allow the scheduling staff the freedom to change the schedules offered by SET.
Each generated schedule can be evaluated according to a variety of performance measures within SET. The output produced includes measures of holding cost, machine utilisation and lateness, including the number of days late and an approximation of the lateness penalty. The measures are calculated over a planning horizon of one month to fit with monthly statistics generated at AEP Flexipac. Click on the following link to view a snapshot of the output produced.
After extensive analysis of the possible objectives to focus on within a Tabu Search framework, it was noted that a weighted objective incorporating a variety of performance measures provided the best results. The weighted objective established a means for balancing conflicting lateness and earliness penalties, thus generating the best results overall. This method generated schedules that improved most performance measures by around 20% when compared to the schedules produced manually.
Analysis of the various rule-based scheduling criteria led to the conclusion that the latest print completion date to ensure on-time completion was the best scheduling criterion. Results from scheduling by this date, followed by family and ink type, were comparative to those provided by Tabu Search. This suggests that if staff at AEP Flexipac chose to automate their scheduling within the current software available, then it would be wise to schedule by these factors.
The implementation of SET at AEP Flexipac would provide a basis for scheduling if desired. However, SET was mainly intended as a prototype to illustrate how a great deal of staff time could be saved if the company moved away from manual scheduling. Even if the scheduling function of SET was not utilised, the evaluation aspect of the package would still be of benefit to AEP Flexipac as a means to provide insights into the efficiency of shop floor operations.
Due to the complex nature of actual scheduling, some assumptions had to be made to reduce the project to a workable size, as fully discussed in the SET User Manual. These limitations mean that any schedule produced by the scheduling package may need to be checked by a staff member to ensure the generated schedules are implementable.
A further limitation is that currently SET schedules and analyses each print machine individually. It would be beneficial to look at the printers collectively as some orders are run on different printers in busy periods. In addition to this, all departments at AEP Flexipac could be incorporated in SET to give a clearer indication of the performance of shop floor operations.
The following references were the most valuable for this project:
Belton, V. and Elder, M., “Exploring a Multicriteria Approach to Production Scheduling,” Journal of the Operational Research Society, 47 (1996), pp 162-174.
Glover, F., “Future paths for integer programming and links to artificial intelligence,” Computers and Operations Research, 13 (5) (1986), pp 533-549.
Glover, F. and Laguna, M., Tabu Search, Kluwer Academic Publishers, (1997)
James, R. and Buchanan, J., “A neighbourhood scheme with a compressed solution space for the early/ tardy scheduling problem,” European Journal of Operational Research, 102 (1997), pp 513-527.
Reeves, C., “Improving the efficiency of tabu search for machine sequencing problems,” Journal of the Operational Research, 44 (1993), pp 375-382
The authors would like to thank past and present staff at AEP Flexipac who made significant contributions of time and knowledge to this project. They would also like to thank their supervisors Dr John Giffin and Dr Cita Wood for providing their expertise.
Jeremy Dodgson and Felicity Noonan completed this project as part of their Management Science Honours project. Please contact them should you have any queries regarding this project.
Jeremy Dodgson and Felicity Noonan