Multiobjective Parallel Algorithms for Solving Biobjective Open Shop Scheduling Problem
Open Shop Scheduling Problem (OSSP) is one of the most important scheduling problems in the field of engineering and industry. This kind of problem includes m machines and n jobs, each job contains a certain number of operations, and each operation has a predetermined processing time on its correspo...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2022-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2022/5043058 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850157702553010176 |
|---|---|
| author | Seyed Hassan Shams Lahroudi Farzaneh Mahalleh Seyedsaeid Mirkamali |
| author_facet | Seyed Hassan Shams Lahroudi Farzaneh Mahalleh Seyedsaeid Mirkamali |
| author_sort | Seyed Hassan Shams Lahroudi |
| collection | DOAJ |
| description | Open Shop Scheduling Problem (OSSP) is one of the most important scheduling problems in the field of engineering and industry. This kind of problem includes m machines and n jobs, each job contains a certain number of operations, and each operation has a predetermined processing time on its corresponding machine. The order of processing of these operations affects the completion times of all jobs. Therefore, the purpose of OSSP is to achieve a proper order of processing of jobs using specified machines, so that the completion time of all jobs is minimized. In this paper, the strengths and limitations of three methods are evaluated by comparing the results of solving the OSSP in large-scale and small-scale benchmarks. In this case, the minimized completion time and total tardiness are considered the objective functions of the adapted methods. To solve small-scale problems, we adapt a mathematical model called Multiobjective Mixed Linear Programming (MOMILP). To solve large-scale problems, two metaheuristic algorithms including Multiobjective Parallel Genetic Algorithm (MOPGA) and Multiobjective Parallel Simulated Annealing (MOPSA) are adapted. In experimental results, we randomly generated small-scale problems to compare MOMILP with the Genetic Algorithm (GA) and Simulate Annealing (SA). To compare MOPSA and MOPGA with the state of the art and show their strengths and limitations, we use a standard large-scale benchmark. The simulation results of the proposed algorithms show that although the MOPSA algorithm is faster, the MOPGA algorithm is more efficient in achieving optimal solutions for large-scale problems compared with other methods. |
| format | Article |
| id | doaj-art-3433c013a1d34c8d8c46d19e6fed8c82 |
| institution | OA Journals |
| issn | 1099-0526 |
| language | English |
| publishDate | 2022-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-3433c013a1d34c8d8c46d19e6fed8c822025-08-20T02:24:05ZengWileyComplexity1099-05262022-01-01202210.1155/2022/5043058Multiobjective Parallel Algorithms for Solving Biobjective Open Shop Scheduling ProblemSeyed Hassan Shams Lahroudi0Farzaneh Mahalleh1Seyedsaeid Mirkamali2Department of Industrial ManagementDepartment of ComputerDepartment of Computer Engineering and ITOpen Shop Scheduling Problem (OSSP) is one of the most important scheduling problems in the field of engineering and industry. This kind of problem includes m machines and n jobs, each job contains a certain number of operations, and each operation has a predetermined processing time on its corresponding machine. The order of processing of these operations affects the completion times of all jobs. Therefore, the purpose of OSSP is to achieve a proper order of processing of jobs using specified machines, so that the completion time of all jobs is minimized. In this paper, the strengths and limitations of three methods are evaluated by comparing the results of solving the OSSP in large-scale and small-scale benchmarks. In this case, the minimized completion time and total tardiness are considered the objective functions of the adapted methods. To solve small-scale problems, we adapt a mathematical model called Multiobjective Mixed Linear Programming (MOMILP). To solve large-scale problems, two metaheuristic algorithms including Multiobjective Parallel Genetic Algorithm (MOPGA) and Multiobjective Parallel Simulated Annealing (MOPSA) are adapted. In experimental results, we randomly generated small-scale problems to compare MOMILP with the Genetic Algorithm (GA) and Simulate Annealing (SA). To compare MOPSA and MOPGA with the state of the art and show their strengths and limitations, we use a standard large-scale benchmark. The simulation results of the proposed algorithms show that although the MOPSA algorithm is faster, the MOPGA algorithm is more efficient in achieving optimal solutions for large-scale problems compared with other methods.http://dx.doi.org/10.1155/2022/5043058 |
| spellingShingle | Seyed Hassan Shams Lahroudi Farzaneh Mahalleh Seyedsaeid Mirkamali Multiobjective Parallel Algorithms for Solving Biobjective Open Shop Scheduling Problem Complexity |
| title | Multiobjective Parallel Algorithms for Solving Biobjective Open Shop Scheduling Problem |
| title_full | Multiobjective Parallel Algorithms for Solving Biobjective Open Shop Scheduling Problem |
| title_fullStr | Multiobjective Parallel Algorithms for Solving Biobjective Open Shop Scheduling Problem |
| title_full_unstemmed | Multiobjective Parallel Algorithms for Solving Biobjective Open Shop Scheduling Problem |
| title_short | Multiobjective Parallel Algorithms for Solving Biobjective Open Shop Scheduling Problem |
| title_sort | multiobjective parallel algorithms for solving biobjective open shop scheduling problem |
| url | http://dx.doi.org/10.1155/2022/5043058 |
| work_keys_str_mv | AT seyedhassanshamslahroudi multiobjectiveparallelalgorithmsforsolvingbiobjectiveopenshopschedulingproblem AT farzanehmahalleh multiobjectiveparallelalgorithmsforsolvingbiobjectiveopenshopschedulingproblem AT seyedsaeidmirkamali multiobjectiveparallelalgorithmsforsolvingbiobjectiveopenshopschedulingproblem |