For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Heuristic Algorithm for One-Machine Just-In-Time Scheduling Problem with Periodic Time Slots
Eishi CHIBA Kunihiko HIRAISHI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2005/05/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
scheduling, just-in-time, set-up times, heuristic algorithm, minimum cost flow,
Full Text: PDF(241.1KB)>>
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.