Scholarlink

<p>We study a single-machine scheduling problem with release times and deterioration effects, where the processing time of jobs are linear functions of their starting times minus release times and deterioration rates. The aim is to find a sequence with the objective function of minimizing the total completion time. To solve this NP-hard problem, some heuristic algorithms (including upper bound algorithm, Nawaz–Enscore–Ham (NEH) algorithm, NEH-enhanced simulated annealing algorithm, dual-phase simulated annealing) and a branch-and-bound algorithm are proposed. Experimental results are conducted to demonstrate the superiority of the heuristic algorithms and the branch-and-bound algorithm, which demonstrates that the branch-and-bound algorithm can solve random instances of 22 jobs within reasonable time and that dual-phase simulated annealing is more accurate than the other heuristic algorithms.</p>

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

Minimizing total completion time scheduling problem with ready times and linear deterioration functions of processing times

  • 期刊论文

  • 发表日期：

    2025年12月8日

查看全文
  • Zheng-Wei Sun,
  • Dan-Yang Lv,
  • Ping Ji,
  • Ji-Bo Wang

摘要

We study a single-machine scheduling problem with release times and deterioration effects, where the processing time of jobs are linear functions of their starting times minus release times and deterioration rates. The aim is to find a sequence with the objective function of minimizing the total completion time. To solve this NP-hard problem, some heuristic algorithms (including upper bound algorithm, Nawaz–Enscore–Ham (NEH) algorithm, NEH-enhanced simulated annealing algorithm, dual-phase simulated annealing) and a branch-and-bound algorithm are proposed. Experimental results are conducted to demonstrate the superiority of the heuristic algorithms and the branch-and-bound algorithm, which demonstrates that the branch-and-bound algorithm can solve random instances of 22 jobs within reasonable time and that dual-phase simulated annealing is more accurate than the other heuristic algorithms.