最小化总完工时间且工件可拒绝的单机双代理多任务排序问题  

The Single-Machine Two-Agent Multi-Task Scheduling Problem with Rejection to Minimize the Total Completion Time

作　　者：张新功 叶爽 ZHANG Xingong;YE Shuang(School of Mathematical Sciences,Chongqing Normal University,Chongqing 401331,China)

机构地区：[1]重庆师范大学数学科学学院,重庆401331

出　　处：《重庆师范大学学报（自然科学版）》2024年第4期61-67,共7页Journal of Chongqing Normal University:Natural Science

基　　金：国家自然科学基金重大项目(No.11991022);“最优化理论与方法及其应用”创新创业示范团队项目(No.CQYC20210309536);重庆市自然科学基金创新发展联合基金项目(No.CSTB2023NSCQ-LZX0005)。

摘　　要：研究了工件可拒绝的双代理单机多任务排序问题。所谓多任务环境即是指当某个工件(主工件)在加工时,会被其余未完成加工的工件(这里称为等待工件)所打扰。而双代理之间不可互相打扰,它们共同使用单台机器来完成各自工件的加工,第1个代理目标函数为最小化总完工时间,第2个代理最大完工时间不超过某个上界。给定总拒绝费用的允许上界,每个工件有2个选择:接受或拒绝。排序目的是为了第2个代理最大完工时间不超过某个上界的条件下,要使得第1个代理目标函数最小化。由于该问题是NP难问题,为该问题给出最优性质刻画和复杂度分析,以及设计了伪多项式动态规划算法。并用算例实验来说明了算法的可行性。It investigates the single-machine multi-task scheduling problem with two-agent 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 NP-hard,it provides the optimal property characterizations and complexity analysis and designs a pseudo-polynomial dynamic programming algorithm.Numerical experiments are conducted to demonstrate the feasibility of the proposed algorithm.

关 键 词：双代理排序 可拒绝 总完工时间 多任务排序 

分 类 号：O223[理学—运筹学与控制论]