An agent-based intelligent algorithm for uniform machine scheduling to minimize total completion time

This paper considers the uniform machine scheduling problem with release dates so as to minimize the total completion time. The problem is known to be NP-hard in the strong sense, even when there is only a single machine. An intelligent scheduling algorithm, called ABISA, is proposed, in which agent technology is introduced to realize the robotization process of manufacturing scheduling by means of the intelligence of the machines. Semantic description of two kinds of agent is given, and token-ring mechanism is presented for agent coordination. A lower bound is derived which is used to evaluate the performance of the algorithms. By examining 1800 random problem instances, the algorithm shows an excellent performance in the solution quality. The results obtained by ABISA are better than the algorithms based on traditional heuristic rules, and are closer to the lower bound of the problem.