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 show...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.展开更多
We consider the resumable version of the two-agent single machine scheduling prob- lems with forbidden intervals in which the jobs cannot be processed. The goal is to minimize the sum of the objective functions of the...We consider the resumable version of the two-agent single machine scheduling prob- lems with forbidden intervals in which the jobs cannot be processed. The goal is to minimize the sum of the objective functions of the two agents. Polynomial and pseudo-polynomial time algorithms are presented for various combinations of regular scheduling objective functions.展开更多
基金Supported by National Natural Science Foundation of China(Grant Nos.11901168,11971443 and 12271491)。
文摘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.
基金Supported by National Natural Science Foundation of China(11401604,11401605,11271338,11326191)National Natural Science Foundation of Henan(132300410392)the Ph.D Programs Foundation of Ministry of Education of China(20111401110005)
文摘We consider the resumable version of the two-agent single machine scheduling prob- lems with forbidden intervals in which the jobs cannot be processed. The goal is to minimize the sum of the objective functions of the two agents. Polynomial and pseudo-polynomial time algorithms are presented for various combinations of regular scheduling objective functions.
