Ant Colony Optimisation for Backward Production Scheduling

The main objective of a production scheduling system is to assign tasks (orders or jobs) to resources and sequence them as efficiently and economically (optimised) as possible. Achieving this goal is a difficult task in complex environment where capacity is usually limited. In these scenarios, finding an optimal solution—if possible—demands a large amount of computer time. For this reason, in many cases, a good solution that is quickly found is preferred. In such situations, the use of metaheuristics is an appropriate strategy. In these last two decades, some out-of-the-shelf systems have been developed using such techniques. This paper presents and analyses the development of a shop-floor scheduling system that uses ant colony optimisation (ACO) in a backward scheduling problem in a manufacturing scenario with single-stage processing, parallel resources, and flexible routings. This scenario was found in a large food industry where the corresponding author worked as consultant for more than a year. This work demonstrates the applicability of this artificial intelligence technique. In fact, ACO proved to be as efficient as branch-and-bound, however, executing much faster. 1. Production Scheduling Still a Differential for Competitiveness The globalised world economic scenario makes entrepreneurial competitiveness unavoidable and being competitive has become an indispensable prerequisite to organisations that strive for success. Within this context, manufacturing activities become especially important for they decisively influence performance, directly affecting (and being affected by) forecast, planning, and scheduling decisions. Shop-floor production scheduling, which within the hierarchical production planning covers disaggregate and detailed decisions in short time frame, consists in allocating activities (production orders or jobs) to resources, by obeying sequencing and setup restrictions, with focus on getting the best possible results from limited available resources, and, at the same time, aiming at reducing production costs and meeting service levels as fast and efficiently as possible. To make all this happen in cases where production and financial resources are limited and restrictions are many, adequate algorithms techniques and intelligence are necessary. Almost four decades ago, Garey et al. [1] classified production scheduling problems as being NP-hard, which in practical ways means that it is very difficult for one to obtain an optimal solution through exact algorithms and also demand unacceptable execution (computer or effort) time. The