A Hybrid Genetic Algorithm for the Open ShopScheduling with Makespan and Total Completion Time

Subject Areas : B. Computer Systems Organization

Behnam Barzegar ¹ , Homayun Motameni ² , Ali Khosrozadeh ghomi ³ , Azadeh Divsalar ⁴

1 - Department of Computer Engineering, Nowshahr Branch, Islamic Azad University, Nowshahr, Iran
2 - Department of Computer Engineering, Sari Branch, Islamic Azad University, Sari, Iran
3 - Department of Computer Engineering, Science and Research Ayatollah Amoli Branch, Islamic Azad University, Amol, Iran
4 - Department of Computer Engineering, Sari Branch, Islamic Azad University, Sari, Iran

Received: 2013-05-08 Accepted : 2013-05-08 Published : 2012-11-01

Keywords: Scheduling, Open shop, Genetics algorithm,

Abstract :

Proper scheduling of tasks leads to optimum using of time and resources, in order to obtaining best result. One of the most important and complicated scheduling problems is open shop scheduling problem. There are n jobs in open shop scheduling problem which should be processed by m machines. Purpose of scheduling open shop problem is attaining to a suitable order of processing jobs by specified machines so that makespan can be minimized. Open shop scheduling problem has very large and complex solution space and so is one of NP-Problems. Till now, different algorithms have been presented for open shop scheduling problem. In this paper, we have used combined genetics algorithm as a strategy for solving scheduling open shop problem and compared proposed algorithm with DGA algorithm. Results show that the proposed algorithm has better effectiveness than DGA algorithm.