A quadratic time algorithm to maximize the number of just-in-time jobs on identical parallel machines

A quadratic time algorithm to maximize the number of just-in-time jobs on identical parallel machines

0.00 Avg rating0 Votes
Article ID: iaor20063298
Country: United Kingdom
Volume: 32
Issue: 12
Start Page Number: 3265
End Page Number: 3271
Publication Date: Dec 2005
Journal: Computers and Operations Research
Authors: ,
Keywords: optimization, production: JIT
Abstract:

In this paper, we study a scheduling problem on identical parallel machines, in which a processing time and a due date are given for each job, and the objective is to maximize the number of just-in-time jobs. A job is called just-in-time if it is completed exactly on its due date. We discuss the known results, show that a recently published greedy algorithm for this problem is incorrect, and present a new quadratic time algorithm which solves the problem.

Reviews

Required fields are marked *. Your email address will not be published.