Abstract:It investigates the singlemachine multitask scheduling problem with twoagent which jobs can be rejected. In a multitasking environment, when a job (referred to here as the main job) is being processed, it can be disturbed by other unfinished jobs (referred to here as waiting jobs). The two agents cannot interfere with each other and share a single machine to process their respective jobs. The objective function for the first agent is to minimize the total completion time, while the maximum completion time for the second agent does not exceed a specified upper bound. Given an allowable upper bound of total rejection cost, each job has two options: accepted or rejected. The aim is to minimize the objective function of the first agent under the condition that the maximum completion time of the second agent does not exceed the specified upper bound. As the proposed problem is NPhard, it provides the optimal property characterizations and complexity analysis and designs a pseudopolynomial dynamic programming algorithm. Numerical experiments are conducted to demonstrate the feasibility of the proposed algorithm.