首页 | 本学科首页   官方微博 | 高级检索  
     


The strong NP-hardness of the maximum lateness minimization scheduling problem with the processing-time based aging effect
Authors:Rados?aw Rudek
Affiliation:Wroc?aw University of Economics, Komandorska 118/120, 53-345 Wroc?aw, Poland
Abstract:In this paper, we analyse the single machine maximum lateness minimization scheduling problem with the processing time based aging effect, where the processing time of each job is described by a non-decreasing function dependent on the sum of the normal processing times of preceded jobs. The computational complexity of this problem was not determined. However, we show it is strongly NP-hard by proving the strong NP-hardness of the single machine maximum completion time minimization problem with this aging model and job deadlines. Furthermore, we determine the boundary between polynomially solvable and NP-hard cases.
Keywords:Scheduling   Deteriorating   Aging effect   Computational complexity
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号