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 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.