A Note on Two-Agent Scheduling with Rejection on a Single Machine

Expand
  • 1. College of Information and Management Science, Henan Agricultural University, Zhengzhou 450003, China; 2. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
: ZHANG Li-qi (1980-), female, native of Anyang, Henan, associate professor of Henan Agricultural University, engages in combinatorial optimization and scheduling theory; ZHOU Song-tao (1991-), male, native of Pingdingshan, Henan, master student of Zhengzhou University, engages in combinatorial optimization and scheduling theory; LU Ling-fa (1979-), male, native of Zhengzhou, Henan, professor of Zhengzhou University, engages in combinatorial optimization and scheduling theory.

Received date: 2022-10-30

  Online published: 2022-12-30

Supported by

 Supported by National Natural Science Foundation of China (Grant Nos. 11901168, 11971443 and 12271491).

Abstract

In a recent paper, Feng et al. [5] (Two-agent scheduling with rejection on a single machine. Appl. Math. Model. 39 (2015) 1183-1193) studied some two-agent scheduling problems with rejection on a single machine. The authors showed that all problems are NP-hard and then provided four dynamic programming algorithms. Unfortunately, we observe that some mistakes are contained in the two dynamic programming algorithms. In this note, we first show by a counter-example that the above two algorithms are incorrect. Furthermore, we also provide two new dynamic programming algorithms to solve the same problems.

Cite this article

ZHANG Li-qi, ZHOU Song-tao, LU Ling-fa . A Note on Two-Agent Scheduling with Rejection on a Single Machine[J]. Chinese Quarterly Journal of Mathematics, 2022 , 37(4) : 394 -402 . DOI: 10.13371/j.cnki.chin.q.j.m.2022.04.007

Outlines

/