An ant colony optimization approach for the proportionate multiprocessor open shop |
| |
Authors: | Adak Zeynep Ar?o?lu Mahmure Övül Bulkan Serol |
| |
Institution: | 1.Department of Industrial Engineering, Gebze Technical University, 41400, Kocaeli, Turkey ;2.Department of Industrial Engineering, Marmara University, 34722, Istanbul, Turkey ; |
| |
Abstract: | Multiprocessor open shop makes a generalization to classical open shop by allowing parallel machines for the same task. Scheduling of this shop environment to minimize the makespan is a strongly NP-Hard problem. Despite its wide application areas in industry, the research in the field is still limited. In this paper, the proportionate case is considered where a task requires a fixed processing time independent of the job identity. A novel highly efficient solution representation is developed for the problem. An ant colony optimization model based on this representation is proposed with makespan minimization objective. It carries out a random exploration of the solution space and allows to search for good solution characteristics in a less time-consuming way. The algorithm performs full exploitation of search knowledge, and it successfully incorporates problem knowledge. To increase solution quality, a local exploration approach analogous to a local search, is further employed on the solution constructed. The proposed algorithm is tested over 100 benchmark instances from the literature. It outperforms the current state-of-the-art algorithm both in terms of solution quality and computational time. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|