江西科学Issue(1)：5-9,5.DOI:10.13990/j.issn1001-3679.2016.01.002
维护时长依赖于机器负载和机器空闲的单机调度问题
Single-machine Scheduling Problem with a Machine Workload Dependent and Machine Idle Time Dependent Maintenance Duration
摘要
Abstract
Consider a single-machine scheduling problem with a maintenance where jobs are non-pre-emptive,the start time of the maintenance is given but the duration of the maintenance is an increas-ing function of the machine workload and the machine idle time before the maintenance,the objective is to minimize the makespan. The problem is divided into three cases for discussion. For each of the first two cases,a polynomial time optimal algorithm is proposed. For the last case,the performance of the LPT algorithm is analyzed and the method to obtain an FPTAS for the case from any FPTAS for the classical knapsack problem is provided.关键词
维护/机器调度/负载/时间表长/算法分析Key words
maintenance/machine scheduling/workload/makespan/algorithm analysis分类
数理科学引用本文复制引用
王宇盛,刘爱华,姜俊坡..维护时长依赖于机器负载和机器空闲的单机调度问题[J].江西科学,2016,(1):5-9,5.基金项目
国家自然科学基金项目（71201022) （）
江西省自然科学基金项目（20122BAB201010)。 （）
