An ant colony optimization approach for the proportionate multiprocessor open shop

Autor: Mahmure Övül Arıoğlu, Zeynep Adak, Serol Bulkan
Přispěvatelé: Adak, Zeynep, Arioglu, Mahmure Ovul, Bulkan, Serol
Rok vydání: 2021
Předmět:
Zdroj: Journal of Combinatorial Optimization. 43:785-817
ISSN: 1573-2886
1382-6905
DOI: 10.1007/s10878-021-00798-y
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: