Scholarlink

<p>The Job-Shop Scheduling Problem (JSSP) stands as one of the most renowned challenges in scheduling. It is characterized as a disjunctive problem, wherein a solution is fully depicted through an oriented disjunctive graph, with earliest starting times computed using a longest path algorithm. The complexity of solving this problem arises in part from the requirement that disjunctive graphs representing solutions must be acyclic. Consequently, enumerating these graphs is feasible for small-scale instances only. A significant advancement in this field, credited to (Bierwith in OR Spektrum 17:87–92, 1995), is the introduction of the ‘vector by repetition’ (commonly known as Bierwith’s vector). Notably, this vector possesses the property that it can be mapped to an acyclic disjunctive graph, thereby enabling the mapping of a vector to a solution. This property has paved the way for highly efficient solution methods, as it restricts the search space to valid (i.e., acyclic) solutions. In this work, we aim to show how Bierwirth’s vector can be incorporated into a Quantum Approximate Optimization Algorithm (QAOA) to address the job-shop problem through a novel quantum approach.</p>

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

Indirect job-shop coding using rank: application to QAOA (IQAOA)

  • 期刊论文

  • 发表日期：

    2026年5月18日

查看全文
  • Eric Bourreau,
  • Gérard Fleury,
  • Philippe Lacomme

摘要

The Job-Shop Scheduling Problem (JSSP) stands as one of the most renowned challenges in scheduling. It is characterized as a disjunctive problem, wherein a solution is fully depicted through an oriented disjunctive graph, with earliest starting times computed using a longest path algorithm. The complexity of solving this problem arises in part from the requirement that disjunctive graphs representing solutions must be acyclic. Consequently, enumerating these graphs is feasible for small-scale instances only. A significant advancement in this field, credited to (Bierwith in OR Spektrum 17:87–92, 1995), is the introduction of the ‘vector by repetition’ (commonly known as Bierwith’s vector). Notably, this vector possesses the property that it can be mapped to an acyclic disjunctive graph, thereby enabling the mapping of a vector to a solution. This property has paved the way for highly efficient solution methods, as it restricts the search space to valid (i.e., acyclic) solutions. In this work, we aim to show how Bierwirth’s vector can be incorporated into a Quantum Approximate Optimization Algorithm (QAOA) to address the job-shop problem through a novel quantum approach.