Presentation | 1994/11/25 Job-shop scheduling by Simulated annealing combined with deterministic local search Takeshi Yamada, Ryohei Nakano, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | The Job Shop Scheduling Problem is one of the most difficult NP- hard combinatorial optimization problems.This research investigates finding near optimal schedules using simulated annealing,stochastic local search mechanism,combined with shifting bottleneck (SB) procedure,problem specific deterministic local search method.New schedules are generated by Giffler and Thompson's active schedule generating method with permuting operations on critical path.Simulated annealing (SA) probabilistically chooses one of the new schedules and probabilistically accepts or rejects it.Modified SB is applied to repair the rejected schedule and accept it in case it is improved over the old schedule.Experimental results show this method can find near optimal schedules for the difficult benchmark problems and can outperform other existing local search algorithms. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Simulated annealing / job-ship scheduling / active schedule / shitting bottlneck |
Paper # | AI94-55 |
Date of Issue |
Conference Information | |
Committee | AI |
---|---|
Conference Date | 1994/11/25(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Artificial Intelligence and Knowledge-Based Processing (AI) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Job-shop scheduling by Simulated annealing combined with deterministic local search |
Sub Title (in English) | |
Keyword(1) | Simulated annealing |
Keyword(2) | job-ship scheduling |
Keyword(3) | active schedule |
Keyword(4) | shitting bottlneck |
1st Author's Name | Takeshi Yamada |
1st Author's Affiliation | Communication Science Labortories,NTT() |
2nd Author's Name | Ryohei Nakano |
2nd Author's Affiliation | Communication Science Labortories,NTT |
Date | 1994/11/25 |
Paper # | AI94-55 |
Volume (vol) | vol.94 |
Number (no) | 374 |
Page | pp.pp.- |
#Pages | 8 |
Date of Issue |