Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
475549 | Computers & Operations Research | 2014 | 6 Pages |
Abstract
We address a two-machine flow shop on-line scheduling problem. Jobs arrive over time. Each job becomes available for processing at its release time after which it must be processed without preemption on the first machine and then on the second machine. The objective is to minimize the makespan. We provide a best possible deterministic on-line algorithm with a competitive ratio of (5+1)/2. Computational experiments on randomly generated problem instances are performed and the results show that the online algorithm is very useful to obtain near-optimal solutions.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Peihai Liu, Xiwen Lu,