This paper considers the unrelated parallel machine scheduling problem with fuzzy processing times (FUPMSP), which is widely exists in electroplating process and many other production processes. In the considered FUPMSP, the triangular fuzzy numbers (TFN) are adopted to characterize the uncertainty in processing times, and a ranking rule based on signed distance is defined to enable quantitative comparison of fuzzy objectives. Since the FUPMSP is NP-hard, a hybrid optimization algorithm that integrates the longest processing time (LPT) rule into a branch-and-bound framework, namely LPT-B&B, is proposed to address it. In the proposed LPT-B&B, the LPT rule is utilized to generate a high-quality initial feasible solution, which serves as the initial upper bound for the branch-and-bound algorithm and can effectively reduce, the search space through pruning strategies. Simultaneously, the fuzzy lower bound calculation derived from the relaxation model dynamically optimizes the expansion order of branch nodes. The experimental results demonstrate that the LPT-B&B algorithm outperforms traditional methods such as Particle Swarm Optimization (PSO), Simulated Annealing (SA), and Genetic Algorithm (GA) in terms of solution quality and computational efficiency.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A LPT-Based Branch and Bound Algorithm for the Fuzzy Unrelated Parallel Machine Scheduling Problem

  • Run Gan,
  • Nai-Kang Yu,
  • Xing-Yi Li,
  • Li-Jun Wang,
  • Nan Chen,
  • Rong Hu,
  • Bin Qian

摘要

This paper considers the unrelated parallel machine scheduling problem with fuzzy processing times (FUPMSP), which is widely exists in electroplating process and many other production processes. In the considered FUPMSP, the triangular fuzzy numbers (TFN) are adopted to characterize the uncertainty in processing times, and a ranking rule based on signed distance is defined to enable quantitative comparison of fuzzy objectives. Since the FUPMSP is NP-hard, a hybrid optimization algorithm that integrates the longest processing time (LPT) rule into a branch-and-bound framework, namely LPT-B&B, is proposed to address it. In the proposed LPT-B&B, the LPT rule is utilized to generate a high-quality initial feasible solution, which serves as the initial upper bound for the branch-and-bound algorithm and can effectively reduce, the search space through pruning strategies. Simultaneously, the fuzzy lower bound calculation derived from the relaxation model dynamically optimizes the expansion order of branch nodes. The experimental results demonstrate that the LPT-B&B algorithm outperforms traditional methods such as Particle Swarm Optimization (PSO), Simulated Annealing (SA), and Genetic Algorithm (GA) in terms of solution quality and computational efficiency.