The following information was submitted:
Transactions: INTERNATIONAL JOURNAL of APPLIED MATHEMATICS AND INFORMATICS
Transactions ID Number: 19-251
Full Name: Nodari Vakhania
Position: Professor
Age: ON
Sex: Male
Address: Science Faculty, UAEM, Av. Universidad 1001 62210 Cuernavaca, Morelos, Mexico
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: A binary search algorithm for a special case of minimizing the lateness on a single machine
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 study the problem of scheduling jobs with release times and due-dates on a single machine with the objective to minimize the maximal job lateness. This problem is strongly NP-hard, however it is known to be polynomially solvable for the case when the processing times of some jobs are restricted to either $p$ or $2p$, for some integer $p$. We present a polynomial-time algorithm when job processing times are less restricted; in particular, when they are mutually divisible. We first consider the case when the following condition holds: for any pair of jobs, if one is longer than another then the due-date of the former job is no larger than that of the latter one. We also study cases when a slight modification of our algorithm gives an optimal solution for the version without the restriction on job due-dates.
Keywords: algorithm, scheduling, single processor, release date, due-date, lateness
EXTENSION of the file: .pdf
Special (Invited) Session: A polynomial-time algorithm for a special case of minimizing the lateness on a single machine
Organizer of the Session: 629-300
How Did you learn about congress:
IP ADDRESS: 189.138.193.23
