Scheduling jobs with equal processing times on a single machine: minimizing maximum lateness and makespan

详细信息    查看全文

• 作者：Alexander A. Lazarev ; Dmitry I. Arkhipov ; Frank Werner
• 关键词：Scheduling ; Single machine ; Equal processing times ; Polynomial algorithms ; Bi ; criteria problem
• 刊名：Optimization Letters
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：11
• 期：1
• 页码：165-177
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Optimization; Operation Research/Decision Theory; Computational Intelligence; Numerical and Computational Physics, Simulation;
• 出版者：Springer Berlin Heidelberg
• ISSN：1862-4480
• 卷排序：11

文摘

The following special case of the classical NP-hard scheduling problem \(1|r_j|L_{\max }\) is considered. There is a set of jobs \(N= \{ 1, 2, \ldots , n \}\) with identical processing times \(p_j=p\) for all jobs \(j \in N\). All jobs have to be processed on a single machine. The optimization criterion is the minimization of maximum lateness \(L_{\max }\). We analyze algorithms for the makespan problem \(1|r_j|C_{\max }\), presented by Garey et al. (SIAM J Comput 10(2):256–269, 1981), Simons (A fast algorithm for single processor scheduling. In: 19th Annual symposium on foundations of computer science (Ann Arbor, Mich., 1978, 1978) and Benson’s algorithm (J Glob Optim 13(1):1–24, 1998) and give two polynomial algorithms to solve the problem under consideration and to construct the Pareto set with respect to the criteria \(L_{\max }\) and \(C_{\max }\). The complexity of the presented algorithms is \(O(Q \cdot n \log n )\) and \(O(n^3 \log n)\), respectively, where \(10^{-Q}\) is the accuracy of the input-output parameters.