关键词: 调度, 单机, 多任务, 效率提升效应, 资源分配

Abstract: Multi-task scheduling is a critical research area within operations research and management, aiming to optimize task completion times and resource consumption by effectively allocating production resources and managing task relationships. Originally proposed in the field of computer systems, multitasking primarily refers to the parallel execution of multiple processes and tasks within a specific time period. In real life, multitasking is a common phenomenon, such as doctors attending to other patients while waiting for test reports or restaurant servers tending to other guests while waiting for food preparation in the kitchen. The main motivations for studying multi-task scheduling can be summarized as follows. Firstly, diverse work styles can significantly improve work efficiency, reduce the fatigue and boredom associated with performing the same tasks for extended periods, and enhance practitioners’ sense of achievement and satisfaction. Additionally, project leaders can gain early insights by partially handling waiting tasks, thereby reducing the uncertainty of such tasks and effectively alleviating anxiety. In today’s fast-paced work environment, multitasking has become an inevitable trend. Many enterprises consider multitasking ability a crucial criterion in recruitment, underscoring the importance and urgency of studying multi-task scheduling. Therefore, in-depth exploration and optimization of multi-task scheduling models not only improve productivity but also help adapt to the complex demands of modern working environments.
In the multi-task scheduling model presented in this paper, two types of tasks are considered: primary tasks and waiting tasks. A primary task is a task selected at a particular point in time, whereas waiting tasks are other tasks that remain available but are not completed while the primary task is in progress. Since primary tasks are not allowed to be replaced, waiting tasks are not completely finished until they are transformed into primary tasks. They can only be partially processed, and these partially processed portions do not need to be reprocessed afterward. The processing of the primary task can be interrupted by the waiting task, thus involving both interruptions and switches in the multi-task scheduling model. We denote the switching time function by f(·) and the interrupting time function by g_i(·). Therefore, the processing time of the primary task consists of three components: the remaining processing time of the primary task, the interruption time caused by the partial processing of waiting tasks, and the switching time of the unprocessed task when the primary task switches with a waiting task.
The core of the multi-task scheduling problem studied in this paper is to examine the variation in job processing time within a single-computer multi-task scheduling environment. We comprehensively consider both the positive effect of the operator’s perception or cognitive level induced by multitasking, i.e., the efficiency improvement effect, and the fatigue effect caused by performing the same job for an extended period, i.e., the degradation effect. Based on these considerations, we also explore the impact of resource allocation on overall processing time. In this paper, two multi-task scheduling models are constructed. The first model considers the processing time affected by linear resource allocation, incorporating both the linear efficiency improvement effect and the degradation effect based on position change. The actual machining time of the workpiece is expressed as:公式; the second model, on the other hand, accounts for the machining time affected by the convexity of resource allocation, in addition to the linear efficiency improvement effect and the degradation effect based on position change. The actual machining time of the workpiece is represented as: 公式. The objective of these models is to minimize the total completion time and resource cost. We integrate the objective of each model into three parts: the part related to processing time, the part related to resources and the constant part. The resource-related coefficient part is first analyzed to find the optimal resource allocation rule, and then the objective function is transformed into an assignment problem to be solved. For each model, we design efficient polynomial time algorithms and provide structural properties of the optimal scheduling. We prove that such problems are polynomial-time solvable for each model and verify the feasibility and effectiveness of the algorithms through arithmetic experiments. We set the ranges of values for parameters such as p_j, a_j, b_j, v_j, etc., by researching in the context of a real industry and referring to numerous experiments in the relevant literature, and then test them using software to generate random data. We demonstrate the proposed algorithm specifically with an example containing six jobs to find the optimal solution and further verify the feasibility and effectiveness of the algorithm. The experimental results show that the total cost incurred by allocating convex resources is less than the total cost incurred by allocating linear resources.
Future research can be extended in the following aspects: Firstly, the multi-task scheduling model can be applied to more practical scenarios, such as multi-computer environments and dynamic task allocation. Secondly, the algorithm can be further optimized to enhance its computational efficiency in large-scale task scheduling problems.

Key words: scheduling, single-machine, multitasking, efficiency improvement effect, resource allocation