摘要
研究带有共同交货期的三台平行机排序问题。工件在加工过程中不允许中断,目标是极大化所有工件的提前完工量,即在交货期前所加工工件(或部分)的总加工时长。由于该问题是NP-难问题,本文应用经典LPT算法来解决该问题。我们证明了LPT算法求解该问题的最坏情况界至多为15/13,并给出实例说明最坏情况界的下界为27/25。
This paper considers the problem of scheduling on three identical machines with a common due date.The preemption is not allowed.The goal is to maximize the total early work of all the jobs,i.e.,the total processing time of all the jobs(or part)completed before the common due date.Since the problem is NP-hard,we apply the classical heuristic,namely longest processing time(LPT),to tackle the problem.We show that the worst-case ratio of LPT is at most 15/13 and the lower bound of the worst-case ratio is at least 27/25 by providing an instance.
作者
周萍
季敏
蒋义伟
ZHOU Ping;JI Min;JIANG Yiwei(College of Humanities,Zhejiang Business College,Hangzhou 310053,Zhejiang,China;School of Management and E-Business,Zhejiang Gongshang University,Hangzhou 310018,Zhejiang,China)
出处
《运筹学学报》
CSCD
北大核心
2022年第3期151-156,共6页
Operations Research Transactions
基金
浙江省教育厅高校国内访问学者“教师专业发展项目”(No.FX2020093)
国家自然科学基金(Nos.11971434,11871327)。