i-manager Publications

A fast algorithm for the weighted interval scheduling problem

Ruwanthini Siyambalapitiya*

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

Periodicity:January - March'2017
DOI : 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.

Keywords

Interval Scheduling, Greedy Algorithm, Upper Bound.

How to Cite this Article?

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

References

[1]. Arkin, E. M., & Silverberg, E. B. (1987). Scheduling jobs with fixed start and end times. Discrete Applied Mathematics, 18(1), 1-8.

[2]. Bar-Noy, A., Guha, S., Naor, J. S., & Schieber, B. (2001). Approximating the throughput of multiple machines in real time scheduling. Journal of Combinatorial Optimization, 4, 307-323.

[4]. Chen, B., Hassin, R., & Tzur, M. (2002). Allocation of bandwidth and storage. IIE Transactions, 34(5), 501-507.

[5]. Crama, Y., Flippo, O. E., Van de Klundert, J., & Spieksma, F. C. (1997). The assembly of printed circuit boards: A case with multiple machines and multiple board types. European Journal of Operational Research, 98(3), 457-472.

[6]. Darmann, A., Pferschy, U., & Schauer, J. (2010). Resource allocation with time intervals. Theoretical Computer Science, 411(49), 4217-4234.

[7]. Erlebach, T., & Spieksma, F. C. (2003). Interval selection: Applications, algorithms, and lower bounds. Journal of Algorithms, 46(1), 27-53.

[8]. Kolen, A. W., Lenstra, J. K., Papadimitriou, C. H., & Spieksma, F. C. (2007). Interval scheduling: A survey. Naval Research Logistics (NRL), 54(5), 530-543.

[9]. Kovalyov, M. Y., Ng, C. T., & Cheng, T. E. (2007). Fixed interval scheduling: Models, applications, computational complexity and algorithms. European Journal of Operational Research, 178(2), 331-342.

[10]. Kroon, L. G., Salomon, M., & Van Wassenhove, L. N. (1995). Exact and approximation algorithms for the operational fixed interval scheduling problem. European Journal of Operational Research, 82(1), 190-205.

[11]. Torng, E. (1998). A unified analysis of paging and caching. Algorithmica, 20(2), 175-200.

If you have access to this article please login to view the article or kindly login to purchase the article

Single Article

	North Americas,UK, Middle East,Europe		India	Rest of world
	USD	EUR	INR	USD-ROW
Online	15	15

ADD TO CART

Options for accessing this content:

If you would like institutional access to this content, please recommend the title to your librarian.
If you already have i-manager's user account: Login above and proceed to purchase the article.
New Users: Please register, then proceed to purchase the article.