Redução do Makespan para Sistemas com Ponderações Temporais Usando um Algoritmo de Busca Clonal

Abstract

The time-optimal control of Time-Weighted Systems (TWS) is an approach that can be used to makespan reduction of Computer-Integrated Manufacturing (CIM) Systems. Unfortunately, the complexity of the TWS algorithms turns even suboptimal solutions com- putationally intractable when dealing with realistic CIM systems with multiple components, stations, and different productions batches. In this paper, we propose some strategies to alleviate the complexity cost of makespan reduction computations using TWS. The strategies consist of: relaxing the need of symmetric imposed mutual exclusions relations between events; using a hashtable algorithm for makespan computations instead of a heap of pieces algorithm; avoiding computation of batch supervisors using a scalable synthesis method; and applying a Clonal Search heuristic for makespan reduction. With this, we obtain the reduction of the computational cost while maintaining the advantages of the TWS approach regarding the reduction of models by representing one task by only one event. The performance of the proposed algorithm is compared with some of the known efficient approaches by means of a realistic CIM example.