Simulation Annealing and Genetic Algorithms for the Single Machine Scheduling Problem

S. Abdul-Razaq, Tariq

	Simulation Annealing and Genetic Algorithms for the Single Machine Scheduling Problem
Al-Mustansiriyah Journal of Science
Article 1, Volume 21, Issue 7, 2010, Pages 24-33
Author
Tariq S. Abdul-Razaq
Abstract
In this paper we consider the problem of scheduling n jobs on a single machine to minimize the total cost of earliness, tardiness and completion time (i.e. to minimize the multiple objective function (MOF) defined by ). Our main contribution is a Branch and Bound (BAB) algorithm with optimal solution. The BAB procedure uses dominance properties to reduce the number of sequences that must be considered. Since our problem is NP-hard, we propose Simulation Annealing (SA) algorithm and a Genetic Algorithm (GA) to solve the problem efficiency. Also develop optimal procedures for the special cases of our problem. We propose a SA procedure which allows the search to escape from local optima. In SA, a probabilistic acceptance rule is used. Any move that results in an improvement in the objective function value, or leaves the value unchanged, is accepted. On the other hand, a move that increases the objective function value by Δ is accepted with probability , where t is a parameter known as the temperature. We also proposed a GA works with a population of solution, where each solution is represented as a sequence. A mating pool of solutions is formed form the current population. Solutions are chosen from the mating pool quality solutions are assigned a higher fitness. Applying crossover operator and mutation operator forms a new population. In this paper we discuss and modify algorithms to find optimal and near optimal solutions to our scheduling problem. Exact algorithms produce optimal solutions, but their running time can not be bounded from above by a polynomial in the size of an instance for NP-hard problem. Approximation algorithms produce solutions in relatively little computation time, but their solutions need not be optimal. Results from computational show that how well the approximate algorithms (SA and GA) are able to solve instances of our problem.

Statistics Article View: 40 PDF Download: 24