A hybrid particle swarm optimization algorithm for single machine scheduling with sequence-dependent setup times and learning effects
This paper deals with the single machine scheduling problem with sequence-dependent setup time and learning effect on processing time, where the objective is to minimize total earliness and tardiness of the jobs. A Mixed Integer Linear Programming (MILP) model capable of solving small-sized problems...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
REA Press
2023-06-01
|
| Series: | Computational Algorithms and Numerical Dimensions |
| Subjects: | |
| Online Access: | https://www.journal-cand.com/article_190873_eec893008f3b91ab54b6df53f7bcebe2.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832580046135492608 |
|---|---|
| author | Payam Chiniforooshan Dragan Marinkovic |
| author_facet | Payam Chiniforooshan Dragan Marinkovic |
| author_sort | Payam Chiniforooshan |
| collection | DOAJ |
| description | This paper deals with the single machine scheduling problem with sequence-dependent setup time and learning effect on processing time, where the objective is to minimize total earliness and tardiness of the jobs. A Mixed Integer Linear Programming (MILP) model capable of solving small-sized problems is proposed to formulate this problem. In view of the NP-hard nature of the problem, the Hybrid Particle Swarm Optimization (HPSO) algorithm is proposed to solve the large-sized problems. In order to utilize Particle Swarm Optimization (PSO) to solve the scheduling problems, the proposed HPSO approach uses a random key representation to encode solutions, which can convert the job sequences to continuous position values. Also, the local search procedure is included within the HPSO to enhance the exploitation of the algorithm. The performance of the proposed HPSO is verified for small and medium-sized problems by comparing its results with the best solution obtained by the LINGO. In order to test the applicability of the proposed algorithm to solve large-sized problems, 120 instances are generated, and the results are compared with a Random Key Genetic Algorithm (RKGA). The results show the effectiveness of the proposed model and algorithm. |
| format | Article |
| id | doaj-art-f8524854921148598d2091a025f2cbb1 |
| institution | Kabale University |
| issn | 2980-7646 2980-9320 |
| language | English |
| publishDate | 2023-06-01 |
| publisher | REA Press |
| record_format | Article |
| series | Computational Algorithms and Numerical Dimensions |
| spelling | doaj-art-f8524854921148598d2091a025f2cbb12025-01-30T11:22:05ZengREA PressComputational Algorithms and Numerical Dimensions2980-76462980-93202023-06-0122748610.22105/cand.2023.190873190873A hybrid particle swarm optimization algorithm for single machine scheduling with sequence-dependent setup times and learning effectsPayam Chiniforooshan0Dragan Marinkovic1Department of Industrial Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran.Department of Structural Mechanics and Analysis, Technische University Berlin, Strasse des 17. Juni 135, 10623 Berlin, Germany.This paper deals with the single machine scheduling problem with sequence-dependent setup time and learning effect on processing time, where the objective is to minimize total earliness and tardiness of the jobs. A Mixed Integer Linear Programming (MILP) model capable of solving small-sized problems is proposed to formulate this problem. In view of the NP-hard nature of the problem, the Hybrid Particle Swarm Optimization (HPSO) algorithm is proposed to solve the large-sized problems. In order to utilize Particle Swarm Optimization (PSO) to solve the scheduling problems, the proposed HPSO approach uses a random key representation to encode solutions, which can convert the job sequences to continuous position values. Also, the local search procedure is included within the HPSO to enhance the exploitation of the algorithm. The performance of the proposed HPSO is verified for small and medium-sized problems by comparing its results with the best solution obtained by the LINGO. In order to test the applicability of the proposed algorithm to solve large-sized problems, 120 instances are generated, and the results are compared with a Random Key Genetic Algorithm (RKGA). The results show the effectiveness of the proposed model and algorithm.https://www.journal-cand.com/article_190873_eec893008f3b91ab54b6df53f7bcebe2.pdfsingle machine schedulingsequence-dependent setup timelearning effectparticle swarm optimizationgenetic algorithm |
| spellingShingle | Payam Chiniforooshan Dragan Marinkovic A hybrid particle swarm optimization algorithm for single machine scheduling with sequence-dependent setup times and learning effects Computational Algorithms and Numerical Dimensions single machine scheduling sequence-dependent setup time learning effect particle swarm optimization genetic algorithm |
| title | A hybrid particle swarm optimization algorithm for single machine scheduling with sequence-dependent setup times and learning effects |
| title_full | A hybrid particle swarm optimization algorithm for single machine scheduling with sequence-dependent setup times and learning effects |
| title_fullStr | A hybrid particle swarm optimization algorithm for single machine scheduling with sequence-dependent setup times and learning effects |
| title_full_unstemmed | A hybrid particle swarm optimization algorithm for single machine scheduling with sequence-dependent setup times and learning effects |
| title_short | A hybrid particle swarm optimization algorithm for single machine scheduling with sequence-dependent setup times and learning effects |
| title_sort | hybrid particle swarm optimization algorithm for single machine scheduling with sequence dependent setup times and learning effects |
| topic | single machine scheduling sequence-dependent setup time learning effect particle swarm optimization genetic algorithm |
| url | https://www.journal-cand.com/article_190873_eec893008f3b91ab54b6df53f7bcebe2.pdf |
| work_keys_str_mv | AT payamchiniforooshan ahybridparticleswarmoptimizationalgorithmforsinglemachineschedulingwithsequencedependentsetuptimesandlearningeffects AT draganmarinkovic ahybridparticleswarmoptimizationalgorithmforsinglemachineschedulingwithsequencedependentsetuptimesandlearningeffects AT payamchiniforooshan hybridparticleswarmoptimizationalgorithmforsinglemachineschedulingwithsequencedependentsetuptimesandlearningeffects AT draganmarinkovic hybridparticleswarmoptimizationalgorithmforsinglemachineschedulingwithsequencedependentsetuptimesandlearningeffects |