Scholarlink

<p>We consider the uniform parallel machines scheduling problem in the context of optimistic bilevel optimization, where two speed options are considered. In this scenario, the leader selects and assigns a subset of jobs to the follower to minimize the weighted number of tardy jobs, while the follower schedules these jobs on a set of uniform machines to minimize the total completion time. This problem has practical applications in Industry 4.0. We show that this problem is <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\mathcal NP\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">N</mi> <mi>P</mi> </mrow> </math></EquationSource> </InlineEquation>-hard in the strong sense by providing a reduction from the Numerical 3-Dimensional Matching problem and we provide a moderately exponential-time dynamic programming algorithm. The problem is solved by means of a concise MIP formulation and a branch-and-bound algorithm that embeds a column generation approach for the lower bound computation. Computational experiments are presented for instances with up to 100 jobs and 4 machines while larger problems are out of reach for the proposed approaches.</p>

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

Solution of a bilevel optimistic scheduling problem on parallel machines

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年5月29日

查看全文
  • Quentin Schau,
  • Olivier Ploton,
  • Vincent T’kindt,
  • Han Hoogeveen,
  • Federico Della Croce,
  • Jippe Hoogeveen

摘要

We consider the uniform parallel machines scheduling problem in the context of optimistic bilevel optimization, where two speed options are considered. In this scenario, the leader selects and assigns a subset of jobs to the follower to minimize the weighted number of tardy jobs, while the follower schedules these jobs on a set of uniform machines to minimize the total completion time. This problem has practical applications in Industry 4.0. We show that this problem is \(\mathcal NP\) N P -hard in the strong sense by providing a reduction from the Numerical 3-Dimensional Matching problem and we provide a moderately exponential-time dynamic programming algorithm. The problem is solved by means of a concise MIP formulation and a branch-and-bound algorithm that embeds a column generation approach for the lower bound computation. Computational experiments are presented for instances with up to 100 jobs and 4 machines while larger problems are out of reach for the proposed approaches.