A Boltzmann-Based Estimation of Distribution Algorithm for a General Resource Scheduling Model

Abstract

Most researchers employed common functional models when managing scheduling problems with controllable processing times. However, in many complicated manufacturing systems with a high diversity of jobs, these functional resource models fail to reflect their specific characteristics. To fulfill these requirements, we apply a more general model, the discrete model. Traditional functional models can be viewed as special cases of such model. In this paper, the discrete model is implemented on a problem of minimizing the weighted resource allocation subject to a common deadline on a single machine. By reducing the problem to a partition problem, we demonstrate that it is NP-complete, which addresses the difficult issue of the guarantee of both the solution quality and time cost. In order to tackle the problem, we develop an estimation of distribution algorithm based on an approximation of the Boltzmann distribution. The approximation strategy represents a tradeoff between complexity and solution accuracy. The results of the experiments conducted on benchmarks show that, compared with other alternative approaches, the proposed algorithm has competitive behavior, obtaining 74 best solutions out of 90 instances.