Scholarlink

<p>We address here the problem of scheduling a set of jobs on a minimal number of identical machines while forbidding <i>idleness</i>: A machine is <i>idle</i> when it is waiting to process a job after processing another job. After analyzing the complexity of this <i>Multi-Machine Non-Idling Scheduling</i> problem, we focus on its preemptive relaxation obtained by restricting ourselves to unit-period jobs. It has been proved that the variant of this problem induced by a fixed number of machines can be solved in polynomial time by implementing an <i>ad hoc</i> recursive scheme. However, the high complexity of this recursive scheme makes that designing exact algorithms able to solve medium size instances remain an issue. We handle this by first reformulating our problem in a way that skips the machines and the jobs, and next designing an exact <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(A^*\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>A</mi> <mo>∗</mo> </msup> </math></EquationSource> </InlineEquation>-type path search algorithm enhanced by constraint propagation mechanisms. We test the efficiency of this approach via numerical tests.</p>

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

Efficient exact algorithms for multi-Machine non-idling unit-job scheduling

  • 期刊论文

  • 发表日期：

    2026年5月24日

查看全文
  • Philippe Chretienne,
  • Alain Quilliot,
  • Hélène Toussaint

摘要

We address here the problem of scheduling a set of jobs on a minimal number of identical machines while forbidding idleness: A machine is idle when it is waiting to process a job after processing another job. After analyzing the complexity of this Multi-Machine Non-Idling Scheduling problem, we focus on its preemptive relaxation obtained by restricting ourselves to unit-period jobs. It has been proved that the variant of this problem induced by a fixed number of machines can be solved in polynomial time by implementing an ad hoc recursive scheme. However, the high complexity of this recursive scheme makes that designing exact algorithms able to solve medium size instances remain an issue. We handle this by first reformulating our problem in a way that skips the machines and the jobs, and next designing an exact \(A^*\) A ∗ -type path search algorithm enhanced by constraint propagation mechanisms. We test the efficiency of this approach via numerical tests.