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.

Purchase Instant Access

PDF
10
USD

250
INR

HTML
10
USD

250
INR

Username / Email
Password
Don't have an account?  Sign Up
  • 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.

We strive to bring you the best. Your feedback is of great value to us. Feel free to post your comments and suggestions.