Scholarlink

<p>Batch scheduling aims to allocate jobs into several batches on batch-processing machines, and thus increases the production efficiency and has pervasive applications. This paper investigates a novel batch-processing machine scheduling problem, in which non-identical machines are capable of processing a batch of jobs simultaneously only if the knapsack constraints are fulfilled. The objectives are to minimize makespan and total energy consumption. The mixed-integer linear programming (MILP) is established, and an exact algorithm is then proposed to tackle such a bi-objective optimization problem. In each step, the makespan is treated as a <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10479_2025_6485_Article_IEq1.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="10" /> </InlineMediaObject> <EquationSource Format="TEX">\(\epsilon \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation>-constraint, and the problem can be thus regarded as a non-identical batch processing machine scheduling problem with a common deadline (NBPMP-DL), aiming to minimize the total energy consumption. A branch-and-price approach along with some acceleration strategies is devised to solve NBPMP-DL efficiently. The novel aspects of our branch-and-price algorithm are the introduction of the new branching scheme, the design of the label-setting method and the branch-and-bound algorithm for the pricing problem. In computational experiments, the presented method’s performance is tested on randomly generated instances, and the results show that, on average, they outperform the off-the-shelf solver and some state-of-art algorithms from literature in a statistical sense.</p>

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

An exact approach for bi-objective non-identical batch processing machines scheduling

  • 期刊论文

  • 发表日期：

    2025年1月21日

查看全文
  • Shaoxiang Zheng,
  • Naiming Xie,
  • Qiao Wu

摘要

Batch scheduling aims to allocate jobs into several batches on batch-processing machines, and thus increases the production efficiency and has pervasive applications. This paper investigates a novel batch-processing machine scheduling problem, in which non-identical machines are capable of processing a batch of jobs simultaneously only if the knapsack constraints are fulfilled. The objectives are to minimize makespan and total energy consumption. The mixed-integer linear programming (MILP) is established, and an exact algorithm is then proposed to tackle such a bi-objective optimization problem. In each step, the makespan is treated as a \(\epsilon \) ϵ -constraint, and the problem can be thus regarded as a non-identical batch processing machine scheduling problem with a common deadline (NBPMP-DL), aiming to minimize the total energy consumption. A branch-and-price approach along with some acceleration strategies is devised to solve NBPMP-DL efficiently. The novel aspects of our branch-and-price algorithm are the introduction of the new branching scheme, the design of the label-setting method and the branch-and-bound algorithm for the pricing problem. In computational experiments, the presented method’s performance is tested on randomly generated instances, and the results show that, on average, they outperform the off-the-shelf solver and some state-of-art algorithms from literature in a statistical sense.