A Novel Parallel Simulated Annealing Methodology to Solve the No-Wait Flow Shop Scheduling Problem with Earliness and Tardiness Objectives

Creative Commons License

Karacan I., ŞENVAR Ö., BULKAN S.

Processes, cilt.11, sa.2, 2023 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 11 Sayı: 2
  • Basım Tarihi: 2023
  • Doi Numarası: 10.3390/pr11020454
  • Dergi Adı: Processes
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Aerospace Database, Communication Abstracts, INSPEC, Metadex, Directory of Open Access Journals, Civil Engineering Abstracts
  • Anahtar Kelimeler: production scheduling, no-wait flow shop scheduling problem, earliness and tardiness, mixed-integer programming, parallel simulated annealing, SETUP TIMES, ALGORITHM, MINIMIZATION, HEURISTICS
  • Marmara Üniversitesi Adresli: Evet

Özet

In this paper, the no-wait flow shop problem with earliness and tardiness objectives is considered. The problem is proven to be NP-hard. Recent no-wait flow shop problem studies focused on familiar objectives, such as makespan, total flow time, and total completion time. However, the problem has limited studies with solution approaches covering the concomitant use of earliness and tardiness objectives. A novel methodology for the parallel simulated annealing algorithm is proposed to solve this problem in order to overcome the runtime drawback of classical simulated annealing and enhance its robustness. The well-known flow shop problem datasets in the literature are utilized for benchmarking the proposed algorithm, along with the classical simulated annealing, variants of tabu search, and particle swarm optimization algorithms. Statistical analyses were performed to compare the runtime and robustness of the algorithms. The results revealed the enhancement of the classical simulated annealing algorithm in terms of time consumption and solution robustness via parallelization. It is also concluded that the proposed algorithm could outperform the benchmark metaheuristics even when run in parallel. The proposed algorithm has a generic structure that can be easily adapted to many combinatorial optimization problems.