An ant colony optimization approach for the proportionate multiprocessor open shop

Creative Commons License


Journal of Combinatorial Optimization, vol.43, no.4, pp.785-817, 2022 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 43 Issue: 4
  • Publication Date: 2022
  • Doi Number: 10.1007/s10878-021-00798-y
  • Journal Name: Journal of Combinatorial Optimization
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Applied Science & Technology Source, Chimica, Compendex, Computer & Applied Sciences, INSPEC, zbMATH
  • Page Numbers: pp.785-817
  • Keywords: Proportionate multiprocessor open shop, Ant colony optimization, Scheduling, Makespan, Implicit stage permutation representation, PHEROMONE EVALUATION, SCHEDULING PROBLEM
  • Kocaeli University Affiliated: No


© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.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.