A branch-and-bound algorithm for the coupled task problem

被引：0
作者：
József Békési
Gábor Galambos
Michael N. Jung
Marcus Oswald
Gerhard Reinelt
机构：
[1] University of Szeged,Department of Computer Sciences, Juhász Gyula Teacher Training Faculty
[2] Universität Heidelberg,Fakultät für Mathematik und Informatik, Institut für Informatik
来源：
Mathematical Methods of Operations Research | 2014年 / 80卷
关键词：
Coupled task problem; Branch-and-bound; Integer programming;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The coupled task problem is to schedule jobs on a single machine where each job consists of two subtasks and where the second subtask has to be started after a given time interval with respect to the first one. The problem has several applications and is NP-hard. In this paper we present a branch-and-bound algorithm for this problem and compare its performance with four integer programming models.
引用
收藏
页码：47 / 81
页数：34
相关论文
共 24 条
[1]  
Ageev AA(2007)Approximation algorithms for UET scheduling problems with exact delays Oper Res Lett 25 533-540
[2]  
Baburin AE(2004)An exact algorithm for scheduling identical coupled tasks Math Methods Oper Res 59 193-203
[3]  
Ahr D(2001)A note on the complexity of scheduling coupled tasks on a single processor J Brazilian Comput Soc 7 23-26
[4]  
Békési J(2004)Radar pulse interleaving for multi-target tracking Nav Res Logist 51 72-94
[5]  
Galambos G(1997)On the complexity of coupled-task scheduling Discret Appl Math 72 141-154
[6]  
Oswald M(1996)Scheduling for a multifunction phased array radar system Eur J Oper Res 90 13-25
[7]  
Reinelt G(2007)Heuristics for a coupled-operation scheduling problem J Oper Res Soc 58 1375-1388
[8]  
Blazewicz J(2005)Interleaving two-phased jobs on a single machine with application to radar pulse interleaving Discret Optim 2 348-361
[9]  
Ecker K(undefined)undefined undefined undefined undefined-undefined
[10]  
Kis T(undefined)undefined undefined undefined undefined-undefined
123