Complexities of four problems on two-agent scheduling

DOI10.1007/s11590-017-1141-xzbMath1403.90378OpenAlexW2604655294MaRDI QIDQ1653276

Jinjiang Yuan

Publication date: 3 August 2018

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-017-1141-x

zbMATH Keywords

schedulingNP-hardnumber of tardy jobstwo-agentpseudo-polynomial time

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items

Pareto-scheduling of two competing agents with their own equal processing times ⋮ Pareto-scheduling with family jobs or ND-agent on a parallel-batch machine to minimize the makespan and maximum cost ⋮ Due-date assignment scheduling involving job-dependent learning effects and convex resource allocation ⋮ Pareto‐optimization of three‐agent scheduling to minimize the total weighted completion time, weighted number of tardy jobs, and total weighted late work ⋮ Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work ⋮ ND-agent scheduling of linear-deteriorating tasks with positional due indices to minimize total completion time and maximum cost ⋮ Scheduling with release dates and preemption to minimize multiple max-form objective functions

Cites Work

• Unnamed Item
• Unnamed Item
• Due dates assignment and JIT scheduling with equal-size jobs
• A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: multi-agent scheduling problems
• Single-machine multi-agent scheduling problems with a global objective function
• A multiple-criterion model for machine scheduling
• Scheduling Problems with Two Competing Agents
• Algorithms for Scheduling Independent Tasks
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs