A first Fit type algorithm for the coupled task scheduling problem with unit execution time and two exact delays

被引：5

作者：

Bekesi, Jozsef ^{[1
]}

Dosa, Gyorgy ^{[2
]}

Galambos, Gabor ^{[3
]}

机构：

[1] Univ Szeged, Dept Comp Algorithms & Artificial Intelligence, POB 652, H-6701 Szeged, Hungary

[2] Pannon Univ, Egyet Str 10, H-8200 Veszprem, Hungary

[3] Univ Szeged, Gyula Juhasz Fac Educ, Dept Appl Informat, POB 361, H-6701 Szeged, Hungary

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2022年 / 297卷 / 03期

关键词：

Combinatorial optimization; Scheduling; Approximation algorithm; APPROXIMATION ALGORITHMS;

D O I：

10.1016/j.ejor.2021.06.002

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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). (C) 2021 Elsevier B.V. All rights reserved.

引用

页码：844 / 852

页数：9

共 11 条

[1] Approximating Coupled-Task Scheduling Problems with Equal Exact Delays [J].

Ageev, Alexander ;

Ivanov, Mikhail .

DISCRETE OPTIMIZATION AND OPERATIONS RESEARCH, DOOR 2016, 2016, 9869 :259-271

[2]

Ageev AA, 2006, LECT NOTES COMPUT SC, V4368, P1

[3] Approximation algorithms for UET scheduling problems with exact delays [J].

Ageev, Alexander A. ;

Baburin, Alexei E. .

OPERATIONS RESEARCH LETTERS, 2007, 35 (04) :533-540

[4] An exact algorithm for scheduling identical coupled tasks [J].

Ahr D. ;

Békési J. ;

Galambos G. ;

Oswald M. ;

Reinelt G. .

Mathematical Methods of Operations Research, 2004, 59 (02) :193-203

[5] Improved analysis of an algorithm for the coupled task problem with UET jobs [J].

Bekesi, Jozsef ;

Galambos, Gabor ;

Oswald, Marcus ;

Reinelt, Gerhard .

OPERATIONS RESEARCH LETTERS, 2009, 37 (02) :93-96

[6]

Graham R. L., 1979, Discrete Optimisation, P287

[7]

Johnson D. S., 1973, Phd thesis

[8] Coupled task scheduling with exact delays: Literature review and models [J].

Khatami, Mostafa ;

Salehipour, Amir ;

Cheng, T. C. E. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2020, 282 (01) :19-39

[9] Scheduling coupled-tasks on a single machine [J].

Li, Haibing ;

Zhao, Hairong .

2007 IEEE SYMPOSIUM ON COMPUTATIONAL INTELLIGENCE IN SCHEDULING, 2007, :137-+

[10] Scheduling for a multifunction phased array radar system [J].

Orman, AJ ;

Potts, CN ;

Shahani, AK ;

Moore, AR .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1996, 90 (01) :13-25

← 1 2 →