数学季刊 ›› 2022, Vol. 37 ›› Issue (4): 394-402.doi: 10.13371/j.cnki.chin.q.j.m.2022.04.007

• • 上一篇    下一篇

关于单机双代理可拒绝排序的一个注记

  

  1. 1. College of Information and Management Science, Henan Agricultural University, Zhengzhou 450003, China; 2. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
  • 收稿日期:2022-10-30 出版日期:2022-12-30 发布日期:2022-12-30
  • 通讯作者: ZHANG Li-qi (1980-), female, native of Anyang, Henan, associate professor of Henan Agricultural University, engages in combinatorial optimization and scheduling theory; E-mail:zhangliqi2013@163.com
  • 作者简介:: 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.
  • 基金资助:
     Supported by National Natural Science Foundation of China (Grant Nos. 11901168, 11971443 and 12271491).

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

  1. 1. College of Information and Management Science, Henan Agricultural University, Zhengzhou 450003, China; 2. School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
  • Received:2022-10-30 Online:2022-12-30 Published:2022-12-30
  • Contact: ZHANG Li-qi (1980-), female, native of Anyang, Henan, associate professor of Henan Agricultural University, engages in combinatorial optimization and scheduling theory; E-mail:zhangliqi2013@163.com
  • About author:: 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.
  • Supported by:
     Supported by National Natural Science Foundation of China (Grant Nos. 11901168, 11971443 and 12271491).

PDF (PC)

62

摘要： 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.

关键词:  , Two-agent scheduling, Single machine, Rejection, Dynamic programming 

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.

Key words:  , Two-agent scheduling, Single machine, Rejection, Dynamic programming 

中图分类号: 

版权所有 © 《数学季刊》编辑部
地址：河南省开封市明伦街85号河南大学数学季刊编辑部
电话：0371-23881698　E-mail: sxjk@henu.edu.cn　QQ: 2454327236
本系统由北京玛格泰克科技发展有限公司设计开发　技术支持：support@magtech.com.cn