Solving the Single Processor Scheduling Problem by Using Ant Colony Optimization Technique

In this paper, we present an efficient programming approach for solving the proposed problem with an analogy, the way ant colonies function has suggested the definition of a new computational paradigm, which we call Ant colony optimization technique. The existing proposal is a single processor-scheduling problem in which the sum of values of all jobs is maximized and also presents a new pheromone updating strategy which is used to optimize ACO (Ant Colony Optimization) technique in solving the Traveling Salesman Problem. The value of a job is characterized by a stepwise no increasing function with one or more moments at which the changes of job value occur. We prove that the special case of our problem, with a single moment of change of job values, is equivalent to the well known, NP-hard in the ordinary sense, problem of minimizing weighted number of late jobs. The technique is realized under Java environment, and applied to solve the proposed problem. Finally, in order to solve the general version of the problem, we construct and experimentally test a number of heuristic algorithms.