An optimal algorithm for preemptive scheduling on non-simultaneously available uniform machines  

作　　者：Hao ZHOU Liping CAO Qi WEI Zhenyu SHU Yiwei JIANG 

机构地区：[1]College of Basic Science,Zhejiang Shuren University,Hangzhou 310015,China [2]School of Management and E-Business,Zhejiang Gongshang University,Hangzhou 310018,China [3]College of International Economics and Trade,Ningbo University of Finance and Economics,Ningbo 315175,China [4]School of Computer and Data Engineering,NingboTech University,Ningbo 315100,China

出　　处：《Frontiers of Information Technology & Electronic Engineering》2025年第3期472-478,共7页信息与电子工程前沿(英文版)

基　　金：supported by the Zhejiang Provincial Natural Science Foundation of China(Nos.LZ23G010001 and LZ25F020012);the National Natural Science Foundation of China(Nos.62172356 and 61872321);the Ningbo Major Special Projects of the“Science and Technology Innovation 2025”(No.2024Z122)。

摘　　要：We study preemptive scheduling on m uniform machines with non-simultaneous available times to minimize the makespan.Each machine has a different speed and a different available time.We first provide a lower bound on the optimal makespan of the problem by converting the real machines to virtual machines that guarantee a machine with an earlier available time having a greater speed at any time.

关 键 词：preemptive scheduling virtual machines converting real machines virtual machines lower bound non simultaneous available times uniform machines MAKESPAN 

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