Two-Client Scheduling with Order Selection
DOI: https://doi.org/10.62517/jbdc.202601224
Author(s)
Qi Feng*, Liangliang Su
Affiliation(s)
School of Mathematics and Information Science, Zhongyuan University of Technology, Zhengzhou, Henan, China
*Corresponding Author
Abstract
The paper addresses two-client scheduling with order selection on a machine. There are two clients G and H. Each having his own item sets. An item of each client needs to be selected before processing. Namely, an item is either selected to accept and process on the machine, or reject but require to pay a certain penalty for rejection. Decision makers want to minimize the sum of objections of accepted items and the rejection penalty of rejected items of client G. But at the same time, the sum of objections of accepted items and the rejection penalty of rejected items of client H can not exceed a constant. For the above problems, we first uncover crucial structural properties. Then analysis several different cases when items are processed on the machine. And develop two algorithms at last.
Keywords
Scheduling; Two-Client; Item; Acceptance; Algorithm
References
[1]Y. Bartal, S. Leonardi, A. M. Spaccamela, et. al. Multiprocessor scheduling with rejection. SIAM Journal on Discrete Mathematics. 2000, 13: 64-78.
[2]A. Agnetis, P. B. Mirchandani, D. Pacciarelli, et.al. Scheduling problems with two competing agents. Operations Research. 2004, 52: 229–242.
[3]A. Agnetis, J. C. Billaut, S. Gawiejnowicz, et.al. Multiagent Scheduling. Springer: Berlin/Heidelberg, Germany, 2014.
[4]C. He, J. Wu, H. Lin. Two-agent bounded parallel-batching scheduling for minimizing maximum cost and makespan. Discrete Optimization. 2022, 45: 100698.
[5]R. X. Chen, S. S. Li. Two‑machine job shop scheduling with optional job rejection. Optimization Letters. 2024, 18: 1593–1618.
[6]T. Rault, F. Sadi, J.C. Billaut, et.al. Scheduling two interfering job sets on identical parallel machines with makespan and total completion time minimization. Journal of Scheduling. 2024, 27: 485–505.
[7]A. Agnetis, M. Benini, G. Nicosia, et.al. Trade-off between utility and fairness in two-agent single-machine scheduling. European Journal of Operational Research. 2025, 323: 767–779.
[8]R.J. Yu, D. Oron. Coordinating two agents in parallel-batching scheduling to minimize the number of late jobs. Computers & Industrial Engineering. 2026: 211, 111625.
[9]Q. Feng, B. Q. Fan, S. S. Li, et.al. Two-agent scheduling with rejection on a single machine. Applied Mathematical Modelling. 2015, 39: 1183–1193.
[10]Q. Feng, S. S. Li. Algorithms for Multi-Customer scheduling with Outsourcing. Mathematics. 2022, 1553(10): 2227-7390.
