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

  • Gabriel Laport Vargas Faculdade de Engenharia de Defesa, Instituto Militar de Engenharia, RJ
  • Antonio Eduardo Carrilho da Cunha Faculdade de Engenharia de Defesa, Instituto Militar de Engenharia, RJ
Keywords: Discrete event systems, Time-weighted systems, Supervisory control, Makespan reduction, Manufacturing


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.