Competing multi-agent scheduling of equal-length jobs on a single machine or uniform parallel machines

We consider the competing multi-agent scheduling problems with equal-length jobs on a single machine or uniform parallel machines. Suppose that there are k agents. When k is arbitrary, the exact complexities of the single-machine feasibility problems with equal-length jobs were unaddressed in the literature, where the objective of each agent is to minimize the total weighted completion time, total tardiness, total weighted number of tardy jobs or total weighted late work. This inspires our research on the competing multi-agent scheduling problems with equal-length jobs. When k is arbitrary, we show that five single-machine feasibility problems with equal-length jobs are unary NP-complete, among which four problems remain unary NP-complete even for unit-length jobs. When k is arbitrary or fixed, we show that two uniform-parallel-machine feasibility problems are solvable in polynomial time through the single-machine generated completion times (GCT) scheduling model. When k is fixed, we present pseudo-polynomial algorithms and (super) fully polynomial time approximation schemes for one single-machine and three uniform-parallel-machine feasibility problems through the GCT scheduling model.