Scholarlink

<p>In this paper, we study eight order acceptance and scheduling (OAS) problems by considering job splitting, a fixed number of distinct processing times, weights or rejection costs, and position-dependent processing times, weights or rejection costs, respectively. In each OAS problem in consideration, each job is either accepted and processed on a single machine, or rejected by paying a rejection cost, and the objective is to minimize the weighted makespan (maximum weighted completion time) of the accepted jobs plus the total rejection cost of the rejected jobs. We show that three of the eight OAS problems can be solved in polynomial time, another three of the eight OAS problems are NP-hard, but the computational complexities of the remaining two OAS problems are open. For each of those three NP-hard problems, we propose a pseudo-polynomial-time dynamic programming algorithm and an efficient approximation algorithm. Based on the vector trimming technique, we also obtain a fully polynomial time approximation scheme (FPTAS) for each of those NP-hard problems.</p>

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

Order acceptance and scheduling with weighted makespan

  • 期刊论文

  • 发表日期：

    2025年3月15日

查看全文
  • Lingfa Lu,
  • Lili Zuo,
  • Liqi Zhang,
  • Jinwen Ou

摘要

In this paper, we study eight order acceptance and scheduling (OAS) problems by considering job splitting, a fixed number of distinct processing times, weights or rejection costs, and position-dependent processing times, weights or rejection costs, respectively. In each OAS problem in consideration, each job is either accepted and processed on a single machine, or rejected by paying a rejection cost, and the objective is to minimize the weighted makespan (maximum weighted completion time) of the accepted jobs plus the total rejection cost of the rejected jobs. We show that three of the eight OAS problems can be solved in polynomial time, another three of the eight OAS problems are NP-hard, but the computational complexities of the remaining two OAS problems are open. For each of those three NP-hard problems, we propose a pseudo-polynomial-time dynamic programming algorithm and an efficient approximation algorithm. Based on the vector trimming technique, we also obtain a fully polynomial time approximation scheme (FPTAS) for each of those NP-hard problems.