A first Fit type algorithm for the coupled task scheduling problem with unit execution time and two exact delays
研究单机环境下每个作业包含两个子任务的耦合任务调度问题，针对只有两种不同延迟时间的特殊情况，提出首次适应递减算法并证明其近似比在1.57894到1.57916之间。
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).