<p>Scheduling is a fundamental combinatorial optimisation problem encountered across various domains. However, these problems are not only NP-hard but also often dynamic, meaning that complete information is not available from the outset. Such problems are typically addressed using reactive approaches like dispatching rules (DRs), which incrementally adapt to changes in the environment. Given the vast number of scheduling problem variants and the difficulty of manually designing effective DRs, genetic programming (GP) has been widely used to automate their development. Until recently, most research has focused on scheduling problems where each machine can process only a single job at a time. However, batch scheduling, in which machines can process multiple jobs simultaneously, has become increasingly relevant in recent years. Despite this, most studies still consider the static variant of the problem, where all information is known in advance. To address this research gap, this study investigates the dynamic unrelated machines batch scheduling problem and applies GP to automatically generate DRs suited to this context. Since batch scheduling introduces an additional decision-making layer, we propose two new scheduling schemes and several terminal nodes to adapt GP for this problem. The approach is validated through an experimental study, demonstrating that automatically designed DRs can significantly outperform existing manually designed DRs from the literature.</p>

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

Automated design of dispatching rules by genetic programming for the unrelated batch scheduling environment

  • Lucija Planinić,
  • Marko Đurasević,
  • Domagoj Jakobović

摘要

Scheduling is a fundamental combinatorial optimisation problem encountered across various domains. However, these problems are not only NP-hard but also often dynamic, meaning that complete information is not available from the outset. Such problems are typically addressed using reactive approaches like dispatching rules (DRs), which incrementally adapt to changes in the environment. Given the vast number of scheduling problem variants and the difficulty of manually designing effective DRs, genetic programming (GP) has been widely used to automate their development. Until recently, most research has focused on scheduling problems where each machine can process only a single job at a time. However, batch scheduling, in which machines can process multiple jobs simultaneously, has become increasingly relevant in recent years. Despite this, most studies still consider the static variant of the problem, where all information is known in advance. To address this research gap, this study investigates the dynamic unrelated machines batch scheduling problem and applies GP to automatically generate DRs suited to this context. Since batch scheduling introduces an additional decision-making layer, we propose two new scheduling schemes and several terminal nodes to adapt GP for this problem. The approach is validated through an experimental study, demonstrating that automatically designed DRs can significantly outperform existing manually designed DRs from the literature.