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

摘要： 基于人们长时间从事一种工作会导致疲劳和厌倦的行为和心理现象,本文考虑的是一个受多任务处理行为现象影响的单机调度环境,在多任务处理下,选定作业的处理会受到其他可用但未完成的作业的打断。本文研究了具有线性工作效率提升的单机多任务调度,这是由于多任务引起的操作者感知或认知水平的正效应,有助于减少实际中断时长,在此模型基础上考虑了基于DeJong效应的退化函数和资源分配影响的加工时间可变的情况。本文分别考虑了线性工作效率提升基础上线性资源分配、线性工作效率提升基础上凸性资源分配两种模型,模型目标为最小化总完工时间和资源成本。针对每个模型,我们设计了有效的多项式时间算法,并给出了最优调度的结构性质,证明了该问题对每个模型都是多项式时间可解的。最后,我们通过算例实验证明了算法的可行性,实验结果显示,工件投入凸性资源所花费的总成本比投入线性资源的总成本要少。

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