A cross-entropy-based population-learning algorithm for discrete-continuous scheduling with continuous resource discretisation

摘要

The problem of scheduling nonpreemtable tasks on parallel identical machines under constraint on discrete resource and requiring, additionally, renewable continuous resource to minimize the schedule length is considered in the paper. A continuous resource is divisible continuously and is allocated to tasks from given intervals in amounts unknown in advance. Task processing rate depends on the allocated amount of the continuous resource. To eliminate time-consuming optimal continuous resource allocation, a problem Θ_z with continuous resource discretisation is introduced. Because Θ_z is NP-hard a population-learning algorithm (PLA2) is proposed to tackle the problem. PLA2 is a population-based approach which takes advantage of the features common to the social education system rather than to the evolutionary processes. The proposed approach is based on the idea of constructing the hybrid algorithm integrating different optimization techniques complementing each other and producing a synergetic effect. Experimental results proved that PLA2 excels known algorithms for solving the considered problem.