An Exact Approach for Multitasking Scheduling with Two Competitive Agents on Identical Parallel Machines

The cloud manufacturing (CMfg) platform serves as a centralized hub for allocating and scheduling tasks to distributed resources. It features a concrete two-agent model that addresses real-world industrial needs: the first agent handles long-term flexible tasks, while the second agent manages urgent short-term tasks, both sharing a common due date. The second agent employs multitasking scheduling, which allows for the flexible suspension and switching of tasks. This paper addresses a novel scheduling problem aimed at minimizing the total weighted completion time of the first agent’s jobs while guaranteeing the second agent’s due date. For single-machine cases, a polynomial algorithm provides an efficient baseline; for parallel machines, an exact branch-and-price approach is developed, where the polynomial method informs the pricing problem and structural properties accelerate convergence. Computational results demonstrate significant improvements: the branch-and-price solves large-sized instances (up to 40 jobs) within 7200 s, outperforming CPLEX, which fails to find solutions for instances with more than 15 jobs. This approach is scalable for industrial cloud manufacturing applications, such as automotive parts production, and is capable of handling both design validation and quality inspection tasks.