摘要

This paper aims to develop an on-line Ant Colony Optimization (ACO) framework, where jobs arrive over time, and at any time we lack knowledge concerning future jobs. A due date is determined upon job arrival, and jobs are sequenced on the machine to optimize the sum of weighted lead times with all due dates met. We propose that each ant is associated with a sequence of waiting jobs with quoted due dates. This waiting sequence is constantly updated over time (whenever a job is selected to be processed or a new job arrives). The on-line schedule is constructed by selecting the first job in the waiting list of the %26quot;best%26quot; ant to process (along with its due date) as the machine becomes available. However, for the ant where this job is not the first one in the list, processing it pushes back the waiting jobs positioned before it. If such push back results in a due date violation, this ant will be eliminated. Further, our ACO framework does not include the iterative procedure due to the characteristics of the on-line problem; this is one difference from the traditional ACO framework besides ant elimination. The computational testing on generated instances shows that our ACO algorithm outperforms an existing effective on-line algorithm in the literature. Also, with local search incorporated using the EDD (Earliest Due Date) rule, improvements can be obtained in both computational outcome and time.

  • 出版日期2012-8