i-manager Publications

A Greedy based Algorithm for the Interval Scheduling Problem

Ruwanthini Siyambalapitiya*

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

Periodicity:September - November'2016
DOI : https://doi.org/10.26634/jcom.4.3.8286

Abstract

In this paper, we consider the interval scheduling problem which is a restricted version of the general scheduling problem. In the general scheduling problem, a given set of jobs need to be processed by a number of machines or processors so as to optimize a certain criterion. We assume that the processing times of the jobs are given. When we impose the additional requirement of starting time for each job, the scheduling problem is known as the interval scheduling problem. In the basic interval scheduling problem, each machine can process at most one job at a time and each machine is continuously available. Each job should be processed until completion, without interruption. The objective is to process all the jobs with a minimum number of machines. Various types of interval scheduling problems arise in computer science, telecommunications, crew scheduling, and in other areas. We propose a greedy based algorithm to solve the basic interval scheduling problem. We also compute a lower bound for the minimum number of machines or processors. Then we apply the algorithm to sets of data for problems of various sizes and show that the solutions obtained are close to optimal.

Keywords

Interval Scheduling, Fixed Starting Times, Lower Bounds, Greedy Algorithm.

How to Cite this Article?

Siyambalapitiya, R. (2016). A Greedy Based Algorithm for the Interval Scheduling Problem. i-manager’s Journal on Computer Science, 4(3), 19-23. https://doi.org/10.26634/jcom.4.3.8286

References

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

[2]. Bhatia, R. Chuzhoy, J., Freund, A., and Naor, J. (2003). “Algorithmic aspects of bandwidth trading”. Proceedings th of the 30 International Conference on Automata, Languages, and Programming, Netherlands, Lecture Notes in Computer Science, Vol. 2719, pp. 751-766.

[3]. Dantzig, G.B., and Fulkerson, D.R. (1954). “Minimizing the number of tankers to meet a fixed schedule”. Naval Research Logistics Quarterly, Vol. 1, pp. 217-222.

[4]. Ford, L.R., and Fulkerson, D.R. (1962). Flows in networks. Princeton University Press, Princeton, New Jersey.

[5]. Gertsbakh, I., and Stern, H.I. (1978). “Minimal resources for fixed and variable job schedules”. Operations Research, Vol. 26, pp. 68-85.

[6]. Gupta, U.I., Lee, D.T., and Leung, J.Y.T. (1979). “An optimal solution for the channel assignment problem”. IEEE Transactions on Computers, Vol. 27, pp. 807-810.

[7]. Hashimoto, A., and Stevens, J. (1971). “Wire routing by optimizing channel assignment within large apertures”. Proceedings of the Eighth Design Automation Workshop, pp. 155-169.

[8]. Hochbaum, D. (1997). Approximation Algorithms for NP-hard Problems, PWS Publishing Company, Boston.

[9]. Ibaraki, T., and Katoh, N. (1988). Resource Allocation Problems: Algorithmic Approaches, The MIT Press, Cambridge.

[10]. Vazirani, V.V., (2002). Approximation Algorithms, Springer, Heidelberg.

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.