Scholarlink

<p>This paper proposes new heuristics for the classic non-preemptive scheduling problem of assigning <i>n</i> jobs on <i>m</i> identical parallel machines, with the objective of minimizing the makespan. Starting from the list scheduling (LS) method, used for example in longest-processing-time-first (LPT)&#xa0;(Graham in SIAM J Appl Math 17(2):416–429, 1969) or SLACK&#xa0;(Della Croce and Scatamacchia in J Sched 23(2):163–176, 2020) heuristics, we derive a branching strategy that also considers assigning a job to the second-best machine, in addition to the first one, the only one usually dealt with in the literature. Throughout the exploration of solutions, we retain only the best solution. This strategy leads to two heuristics, designed to speed up the solution search. The first, called branch-and-parallelize LS (BPLS), parallelizes the two alternatives considered on each job. The second, branch-and-bound list scheduling (BBLS), applies a branch-and-bound method to widely prune the solution tree. As a trade-off between computation time and solution quality, these heuristics are parameterized in order to assign only a subset of jobs according to the branching strategy. Out of this subset, the assignment is made by the classic LS, that is, each time on the first available machine. We show from instances in the literature that our heuristics outperform many well-known algorithms on the vast majority of the cases considered. We also investigate the subspace of instances for which our heuristics are not able to beat all of these algorithms. Finally, we propose an ad hoc heuristic named MULTI-BBLS (MBBLS) which consists of multiple calls to BBLS that allow it to rank first even on this instance subspace.</p>

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

Branching list scheduling algorithms for the identical parallel machine scheduling problem

  • 期刊论文

  • 发表日期：

    2026年6月26日

查看全文
  • Hakim Hadj-Djilani,
  • Louis-Claude Canon,
  • Laurent Philippe,
  • Julien Bernard

摘要

This paper proposes new heuristics for the classic non-preemptive scheduling problem of assigning n jobs on m identical parallel machines, with the objective of minimizing the makespan. Starting from the list scheduling (LS) method, used for example in longest-processing-time-first (LPT) (Graham in SIAM J Appl Math 17(2):416–429, 1969) or SLACK (Della Croce and Scatamacchia in J Sched 23(2):163–176, 2020) heuristics, we derive a branching strategy that also considers assigning a job to the second-best machine, in addition to the first one, the only one usually dealt with in the literature. Throughout the exploration of solutions, we retain only the best solution. This strategy leads to two heuristics, designed to speed up the solution search. The first, called branch-and-parallelize LS (BPLS), parallelizes the two alternatives considered on each job. The second, branch-and-bound list scheduling (BBLS), applies a branch-and-bound method to widely prune the solution tree. As a trade-off between computation time and solution quality, these heuristics are parameterized in order to assign only a subset of jobs according to the branching strategy. Out of this subset, the assignment is made by the classic LS, that is, each time on the first available machine. We show from instances in the literature that our heuristics outperform many well-known algorithms on the vast majority of the cases considered. We also investigate the subspace of instances for which our heuristics are not able to beat all of these algorithms. Finally, we propose an ad hoc heuristic named MULTI-BBLS (MBBLS) which consists of multiple calls to BBLS that allow it to rank first even on this instance subspace.