Heuristics for parallel-machine flexible-resource scheduling problems with unspecified job assignment

In this paper, we examine the parallel-machine flexible-resource scheduling problem in which job assignment to machines is not specified (UPMFRS). The UPMFRS problem is NP-hard, motivating the development of effective heuristics that approximately determine the job assignment to machines and the allocation of resources to jobs. The paper compares a decomposition heuristic and a tabu-search heuristic, and concludes that the tabu-search heuristic is cost and quality effective in locating the near-optimal solutions.