A note on a two-agent scheduling problem related to the total weighted late work

作者：Zhang, Yuan; Yuan, Jinjiang^*

来源：Journal of Combinatorial Optimization, 2019, 37(3): 989-999.

DOI：10.1007/s10878-018-0337-z

• Scheduling
• Single machine
• Two-agent
• Late work

We revisit a two-agent scheduling problem in which a set of jobs belonging to two agents A and B (without common jobs) will be processed on a single machine for minimizing the total weighted late work of agent A subject to the maximum cost of agent B being bounded. Zhang and Wang (J Comb Optim 33:945-955, 2017) studied three versions of the problem: (i) the A-jobs having a common due date, (ii) the A-jobs having a common processing time, (iii) the general version. The authors presented polynomial-time algorithms for the first two versions and a pseudo-polynomial-time algorithm for the last one. However, their algorithm for the first version is invalid. Then we show the NP-hardness and provide a pseudo-polynomial-time algorithm for the first version with the cost of agent B being makespan, present a polynomial-time algorithm for an extension of the second version, and show that the third version is solvable in pseudo-polynomial-time by a new technique.

• 出版日期2019-4
• 单位郑州大学