Exploring a Resolution Method Based on an Evolutionary Game-Theoretical Model for Minimizing the Machines with Limited Workload Capacity and Interval Constraints

摘要

We present an extension of the machines minimization for scheduling jobs with interval constraints, adding a limited machines workload capacity. We are motivated by the fixed-speed processors minimization problem subject to energy constraints, in which the time resolution is a critical factor for the quality of service in the system. We propose a mixed integer linear programming (MILP) model for an exact solution and explore an alternative resolution method based on a non-cooperative evolutionary theoretical-game model. Our resolution method guarantees a feasible solution to the problem and the computational experiments with a timeout of 3 minutes show that it finds a solution with a number of machines less than or equal to the number of machines for a 97,19% of instances in comparison with the MILP solution over CPLEX 12.6.1.0, in only deciseconds.