A first Fit type algorithm for the coupled task scheduling problem with unit execution time and two exact delays
József Békési, György Dósa, Gábor Galambos
Abstract
The considered coupled task problem (CTP) is to schedule n jobs, each consisting of two (sub)tasks, on a single machine. Exact delay times are between the subtasks of a job and the makespan has to be minimized. It has been proven that the problem is strongly NP-hard in general case (see Orman and Potts (1997)), even if the lengths of the subtasks are identical. This paper considers a special case of CTP where there are jobs with two different delay times only. The complexity status of this problem is unknown. We will present an algorithm – called First Fit Decreasing (FFD) – and we will prove that its approximation ratio is in the interval (1.57894,1.57916).
Topics & Concepts
Job shop schedulingComputer scienceTask (project management)Scheduling (production processes)ScheduleAlgorithmMathematical optimizationInterval (graph theory)Computational complexity theoryExecution timeMathematicsCombinatoricsParallel computingEconomicsOperating systemManagementScheduling and Optimization AlgorithmsOptimization and Search ProblemsDistributed and Parallel Computing Systems