About One Algorithm for Solving Scheduling Problem

作     者：Shulgina, O. N. Shcherbakova, N. K. 

作者机构：Kazan Fed Univ Kremlevskaya ul 18 Kazan 420008 Russia 

出 版 物：《LOBACHEVSKII JOURNAL OF MATHEMATICS》 (罗巴切夫斯基数学杂志)

年 卷 期：2015年第36卷第2期

页      面：211-214页

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：scheduling lateness sequencing pseudopolynomial algorithm properties NP-completeness complexity 

摘      要：In this paper we proved the new properties optimal schedules for unknown strongly NPcomplete scheduling problem of minimizing maximum lateness on a single machine, not allowing preemption. Pseudopolynomial implementation of the general scheme for solving that problem based on these properties is developed.