A Heuristic Algorithm for One-Machine Just-In-Time Scheduling Problem with Periodic Time Slots

Eishi CHIBA  Kunihiko HIRAISHI 

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  Vol.E88-A  No.5  pp.1192-1199
Publication Date: 2005/05/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
scheduling,  just-in-time,  set-up times,  heuristic algorithm,  minimum cost flow, 

Full Text: PDF(242.8KB)

Summary: 
Just-in-time scheduling problem is the problem of finding an optimal schedule such that each job finishes exactly at its due date. We study the problem under a realistic assumption called periodic time slots. In this paper, we prove that this problem cannot be approximated, assuming P≠NP. Next, we present a heuristic algorithm, assuming that the number of machines is one. The key idea is a reduction of the problem to a network flow problem. The heuristic algorithm is fast because its main part consists of computation of the minimum cost flow that dominates the total time. Our algorithm is O(n3) in the worst case, where n is the number of jobs. Next, we show some simulation results. Finally, we show cases in which our algorithm returns an optimal schedule and is a factor 1.5 approximation algorithm, respectively, and also give an approximation ratio depending on the upper bound of set-up times.