2011/12/19 by Damien Prot, Prot, D., Odile Bellenguez‐Morineau +3
Engineering · #Assembly Line Balancing Optimization #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Packing Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.1112.4400
openalex publication_date 2011/12/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we are interested in parallel identical machine scheduling problems with preemption and release dates in case of a regular criterion to be minimized. We show that solutions having a permutation flow shop structure are dominant if there exists an optimal solution with completion times scheduled in the same order as the release dates, or if there is no release date. We also prove that, for a subclass of these problems, the completion times of all jobs can be ordered in an optimal solution. Using these two results, we provide new results on polynomially solvable problems and hence refine the boundary between P and NP for these problems.