Please login using the form on menu list.|
It is required to login for Full-Text PDF.
A Heuristic Algorithm for One-Machine Just-In-Time Scheduling Problem with Periodic Time Slots
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Vol.E88-A No.5 pp.1192-1199
Publication Date: 2005/05/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
minimum cost flow,
Full Text: PDF(242.8KB)
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.