文章基本信息

标题：Minimization of maximum lateness with equal processing times for single machine ∗ ∗ Supported by RFBR-RZD grant 13-08-13190
本地全文：下载
作者：Alexander A. Lazarev ; Alexander A. Lazarev ; Dmitry I. Arkhipov 等
期刊名称：IFAC PapersOnLine
印刷版ISSN：2405-8963
出版年度：2015
卷号：48
期号：3
页码：806-809
DOI：10.1016/j.ifacol.2015.06.182
语种：English
出版社：Elsevier
摘要：Abstract The following case of the classical NP-hard scheduling problem is considered. There is a set of jobs N with identical processing times p = const. All jobs have to be processed on a single machine. The objective function is minimization of maximum lateness. We analyze algorithms for the makespan problem, presented by Garey et al. (1981) and Simons (1978) and represent two polynomial algorithms to solve the problem and to construct the Pareto set with respect to criteria Lmax and C max. The complexity of presented algorithms equals O(Q n log n) and O(n 2 log n), where 10-Q is the accuracy of the input-output parameters.
关键词：Keywordsschedulingunit-time jobspolynomial algorithmsdynamic programming