2017/09/13 by Danny Hermelin, Dvir Shabtay, Hermelin, Danny +3
Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.1709.04169
openalex publication_date 2017/09/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Since its development in the early 90's, parameterized complexity has been\nwidely used to analyze the tractability of many NP-hard combinatorial\noptimization problems with respect to various types of problem parameters.\nWhile the generic nature of the framework allows the analysis of any\ncombinatorial problem, the main focus along the years was on analyzing graph\nproblems. In this paper we diverge from this trend by studying the\nparameterized complexity of Just-In-Time (JIT) flow-shop scheduling problems.\nOur analysis focuses on the case where the number of due dates is considerably\nsmaller than the number of jobs, and can thus be considered as a parameter. We\nprove that the two-machine problem is W[1]-hard with respect to this parameter,\neven if all processing times on the second machine are of unit length, while\nthe problem is in XP even for a parameterized number of machines. We then move\non to study the tractability of the problem when combining the different number\nof due dates with either the number of different weights or the number of\ndifferent processing times on the first machine. We prove that in both cases\nthe problem is fixed-parameter tractable for the two machine case, and is\nW[1]-hard for three or more machines.\n