The following information was submitted:
Transactions: INTERNATIONAL JOURNAL of COMPUTERS
Transactions ID Number: 19-240
Full Name: Nodari Vakhania
Position: Professor
Age: ON
Sex: Male
Address: Science Faculty, UAEM, Av. Universidad 1001 62210 Cuernavaca, Morelos
Country: MEXICO
Tel: 777 329 70 20
Tel prefix: 52
Fax: 777 329 70 40
E-mail address: nodari@uaem.mx
Other E-mails:
Title of the Paper: Fast algorithms for preemptive scheduling of jobs with release times on a single processor to minimize the number of late jobs
Authors as they appear in the Paper: Nodari Vakhania
Email addresses of all the authors: nodari@uaem.mx
Number of paper pages: 9
Abstract: We have $n$ jobs with release times and due-dates to be scheduled preemptively on a single-machine that can handle at most one job at a time. Our objective is to minimize the number of late jobs, ones completed after their due-dates. This problem is known to be solvable in time $O(n^3\log n)$. Here we present two polynomial-time algorithms with a superior running time. The first algorithm solves optimally in time $O(n^2)$ the special case of the problem when job processing times and due-dates are tied so that for each pair of jobs $i,j$ with $d_i>d_j$, $p_i \ge p_j$. This particular setting has real-life applications. The second algorithm runs in time $O(n\log n)$ and works for the general version of the problem. As we show, there are strong cases when the algorithm finds an optimal solution.
Keywords: scheduling single processor, preemption, release date, due date, late job, algorithm
EXTENSION of the file: .pdf
Special (Invited) Session: Preemptive scheduling of jobs with tied parameters on a single processor to minimize the number of late jobs
Organizer of the Session: 629-115
How Did you learn about congress:
IP ADDRESS: 189.138.250.198
