On scheduling models for the frequency interval assignment problem with cumulative interferences. Issue 5 (3rd May 2016)

• Record Type: Journal Article
• Authors: Kiatmanaroj, Kata; Artigues, Christian; Houssin, Laurent
• Is Part Of: Engineering optimization. Volume 48:Issue 5(2016)
• Page Start: 740
• Page End: 755
• Publication Date: 2016-05-03
• Subjects: frequency assignment -- scheduling -- cumulative interferences -- disjunctive graphs -- maximalcliques; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2015.1056789
• Languages: English
• ISSNs: 0305-215X

Abstract

Abstract : In this article, models and methods for solving a real-life frequency assignment problem based on scheduling theory are investigated. A realistic frequency assignment problem involving cumulative interference constraints in which the aim is to maximize the number of assigned users is considered. If interferences are assumed to be binary, a multiple carrier frequency assignment problem can be treated as a disjunctive scheduling problem since a user requesting a number of contiguous frequencies can be considered as a non-preemptive task with a processing time, and two interfering users can be modelled through a disjunctive constraint on the corresponding tasks. A binary interference version of the problem is constructed and a disjunctive scheduling model is derived. Based on the binary representation, two models are proposed. The first one relies on an interference matrix and the second one considers maximal cliques. A third, cumulative, model that yields a new class of scheduling problems is also proposed. Computational experiments show that the case-study frequency assignment problem can be solved efficiently with disjunctive scheduling techniques.