On the variable common due date, minimal tardy jobs bicriteria\n two-machine flow shop problem with ordered machines

2013/07/24 by Aleksandar Ilić, Ilic, Aleksandar
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems #Scheduling and Optimization Algorithms

paper · pdf · doi:10.48550/arxiv.1307.6505

openalex publication_date 2013/07/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider a special case of the ordinary NP-hard two-machine flow shop\nproblem with the objective of determining simultaneously a minimal common due\ndate and the minimal number of tardy jobs. In [S. S. Panwalkar, C. Koulamas, An\nO(n²) algorithm for the variable common due date, minimal tardy jobs\nbicriteria two-machine flow shop problem with ordered machines, European\nJournal of Operational Research 221 (2012), 7-13.], the authors presented\nquadratic algorithm for the problem when each job has its smaller processing\ntime on the first machine. In this note, we improve the running time of the\nalgorithm to O(n log n) by efficient implementation using recently introduced\nmodified binary tree data structure.\n

Related

• Revisiting Johnson's rule for minimizing makespan in the Two-Machine Flow Shop scheduling problem
• Two-stage flow shop scheduling with dedicated machines
• Approximating the 2-Machine Flow Shop Problem with Exact Delays Taking\n Two Values
• Common Due-Date Problem: Exact Polynomial Algorithms for a Given Job Sequence
• On The Parameterized Tractability of the Just-In-Time Flow-Shop\n Scheduling Problem