Scheduling with Multitasking and Outsourcing

In the presence of multitasking, a worker has to concurrently handle interruptions from the waiting jobs and routine jobs while processing a primary job. For over a decade, various studies in this research direction have been conducted aiming to figure out how jobs are scheduled so as to reduce the effect due to multitasking. In this paper, two late-job problems in line with the classical late-job problems are tackled. In contrast to the classical setting in which all jobs must be completed, we suggest the idea of outsourcing. Some jobs are outsourced. Thus, the worker only processes the on-time jobs and handles the interruptions from the waiting jobs. Each outsourced job is assigned to a single freelancer to ensure that all jobs are completed on-time. The overhead is the charges to the freelancers, i.e., the total outsourcing cost. If the service charges of all the jobs are the same, the late-job problem is called the total number of outsourcing jobs (TNOJ) problem, which is in-line with the classical total number of late-job problems. If the service charges are different, the late-job problem is called the total weighted number of outsourcing jobs (TWNOJ) problem, which is in-line with the classical total weighted number of late-job problems. For general settings, it is proved that the TNOJ problem is NP-hard and the TWNOJ problem is strongly NP-hard. If the interruption of a waiting job is proportional to its remaining processing time, the TNOJ problem can be solved in O(nlog(n)P)-time and the TWNOJ problem can be solved in O(nP2)-time, where n is the number of jobs and P denotes the sum of their processing times.