Scholarlink

<p>We consider a one-machine scheduling problem where the temperature of a job rises during processing and cools down when not being processed according to given linear heating and cooling rates. No job’s temperature is allowed to rise above a given threshold, and no job’s temperature can cool below 0. Another crucial property of our problem is that jobs can be preempted an arbitrary number of times, and even more, we allow that a job is processed for an infinitely small amount of time. We consider two objectives: minimize the makespan and minimize the sum of completion times. Our results are as follows. We show how to compactly represent a solution. Further, we prove that the problem of minimizing the sum of completion times can be solved in polynomial time by formulating it as a linear program and deriving a structural property. This result can be extended to hold for any number of machines. Further, we show that a minimum makespan can be found in&#xa0;<i>O</i>(<i>n</i>) time, even when heating and cooling rates are job-dependent.</p>

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

Scheduling cool jobs when processing heats them

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年2月11日

查看全文
  • Roel Lambers,
  • Rudi Pendavingh,
  • Frits C. R. Spieksma,
  • Céline M. F. Swennenhuis

摘要

We consider a one-machine scheduling problem where the temperature of a job rises during processing and cools down when not being processed according to given linear heating and cooling rates. No job’s temperature is allowed to rise above a given threshold, and no job’s temperature can cool below 0. Another crucial property of our problem is that jobs can be preempted an arbitrary number of times, and even more, we allow that a job is processed for an infinitely small amount of time. We consider two objectives: minimize the makespan and minimize the sum of completion times. Our results are as follows. We show how to compactly represent a solution. Further, we prove that the problem of minimizing the sum of completion times can be solved in polynomial time by formulating it as a linear program and deriving a structural property. This result can be extended to hold for any number of machines. Further, we show that a minimum makespan can be found in O(n) time, even when heating and cooling rates are job-dependent.