LP-CICA - Heuristic to improve computational times of single machine distributed scheduling problems
Conference Paper
Overview
Additional Document Info
View All
Overview
abstract
We consider a single machine scheduling problem where autonomous decision makers exist in each of multiple sub-production systems. Sub-production systems independently maintain their own jobs to schedule while communicating with each other to pursue a global goal of minimizing total weighted completion times of the jobs. The primary assumption is that none of the sub-production system and shared machine has complete knowledge about the entire system. CICA (Cooperative Interaction via Coupling Agents) methodology was proposed to apply to the described scheduling problems and tested with small size of jobs. Although CICA algorithm generated promising results, it also showed the limitation to deal with the problems with large size of jobs. Thus, we develop a heuristic to efficiently solve the established single machine scheduling problems, i.e. reduce the computational time in a practical range even for the problems of large job sets. The heuristic is developed based on LP relaxation formulation of the associated single machine scheduling problems, modifying to specifically address the current problem. The experimental results show significant improvement in computational time with still maintaining the solution qualities in reasonable levels.
