A fast algorithm for the weighted interval scheduling problem

Volume 11 Issue 3 January - March 2017

Research Paper

A fast algorithm for the weighted interval scheduling problem

Ruwanthini Siyambalapitiya*

Senior Lecturer, Department of Statistics & Computer Science, University of Peradeniya, Srilanka.

Siyambalapitiya, R. (2017). A fast algorithm for the weighted interval scheduling problem. i-manager’s Journal on Software Engineering, 11(3), 40-44. https://doi.org/10.26634/jse.11.3.13633

Abstract

Placing a set of activities or jobs along a timeline is known as scheduling. The interval scheduling problem arises when each job is specified by an interval with starting and finishing times of each job. It will become a weighted interval scheduling problem when a weight or a value is associated with each job. In this paper, the aim is to maximize the total weight of the jobs that could be scheduled without overlapping. A fast algorithm is presented to solve this problem. An upper bound for the total weight is computed and it is shown that the gap between the solutions to the test problems and the upper bound is extremely small.