Title: Efficient mixed-integer linear programming formulations for the satellite broadcast scheduling problem

Authors: S. Ananthu Krishna; B.S. Girish; Devendra Prakash Ghate

Addresses: Department of Aerospace Engineering, Indian Institute of Space Science and Technology, Valiamala P.O., Thiruvananthapuram – 695547, Kerala, India ' Department of Aerospace Engineering, Indian Institute of Space Science and Technology, Valiamala P.O., Thiruvananthapuram – 695547, Kerala, India ' Department of Aerospace Engineering, Indian Institute of Space Science and Technology, Valiamala P.O., Thiruvananthapuram – 695547, Kerala, India

Abstract: Satellite broadcast scheduling problem (SBSP) is an important optimisation problem in satellite communication systems and is known to be NP-complete. The existing state-of-the-art solution methodologies for the SBSP include neural networks, evolutionary algorithms, and other heuristic approaches. This paper proposes two new mixed-integer linear programming (MILP) formulations for the problem. The performance of the proposed MILP formulations has been evaluated using benchmark problem instances and several other test instances on a commercial MILP solver. Computational results show that the proposed formulations outperform the existing approaches in terms of solution accuracy and computation time.

Keywords: satellite communications; satellite broadcast scheduling; NP-complete problem; mixed-integer linear programming.

DOI: 10.1504/IJOR.2024.142251

International Journal of Operational Research, 2024 Vol.51 No.2, pp.233 - 259

Received: 30 Jun 2021
Accepted: 24 Dec 2021
Published online: 16 Oct 2024 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article