Constraint-based ACO for a shared resource constrained scheduling problem |
| |
Authors: | Dhananjay Thiruvady Gaurav Singh Andreas T. Ernst Bernd Meyer |
| |
Affiliation: | 1. Clayton School of Information Technology, Monash University, Australia;2. CSIRO Mathematics, Informatics and Statistics, Australia |
| |
Abstract: | We consider a scheduling problem arising in the mining industry. Ore from several mining sites must be transferred to ports to be loaded on ships in a timely manner. In doing so, several constraints must be met which involve transporting the ore and deadlines. These deadlines are two-fold: there is a preferred deadline by which the ships should be loaded and there is a final deadline by which time the ships must be loaded. Corresponding to the two types of deadlines, each task is associated with a soft and hard due time. The objective is to minimize the cumulative tardiness, measured using the soft due times, across all tasks. This problem can be formulated as a resource constrained job scheduling problem where several tasks must be scheduled on multiple machines satisfying precedence and resource constraints and an objective to minimize total weighted tardiness. For this problem we present hybrids of ant colony optimization, Beam search and constraint programming. These algorithms have previously shown to be effective on similar tightly-constrained combinatorial optimization problems. We show that the hybrid involving all three algorithms provides the best solutions, particularly with respect to feasibility. We also investigate alternative estimates for guiding the Beam search component of our algorithms and show that stochastic sampling is the most effective. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|