Scholarlink

<p>The most popular and cited model of batch scheduling was introduced and solved almost four decades ago. This pioneering model assumed a single machine, serial batching of unit-time jobs and batch-independent setup times. In the current note, we extend this setting by (i) allowing job-rejection, and (ii) considering flowshop and openshop. The objective function contains two cost components: sum of job completion times and total rejection cost. We introduce approximation algorithms for these problems, which are based on solving to optimality the relaxed versions (allowing non-integer batches) in the first stage, followed by rounding procedures to create integer batches. The results of our numerical tests verify that these efficient approximation algorithms produce very close-to-optimal schedules.</p>

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

A note: approximation algorithms for batch scheduling on shops with job rejection

  • 期刊论文

  • 发表日期：

    2025年5月13日

查看全文
  • Gur Mosheiov,
  • Assaf Sarig

摘要

The most popular and cited model of batch scheduling was introduced and solved almost four decades ago. This pioneering model assumed a single machine, serial batching of unit-time jobs and batch-independent setup times. In the current note, we extend this setting by (i) allowing job-rejection, and (ii) considering flowshop and openshop. The objective function contains two cost components: sum of job completion times and total rejection cost. We introduce approximation algorithms for these problems, which are based on solving to optimality the relaxed versions (allowing non-integer batches) in the first stage, followed by rounding procedures to create integer batches. The results of our numerical tests verify that these efficient approximation algorithms produce very close-to-optimal schedules.