Summary
|
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 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: DOI: 10.1093/ietfec/e88-a.5.1192 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(241.1KB)>>
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. | ||||||||||
| ||||||||||
