Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10347945 | Computers & Operations Research | 2013 | 12 Pages |
Abstract
This paper considers flowshop scheduling problems where job processing times are described by position dependent functions, i.e., dependent on the number of processed jobs, that model learning or aging effects. We prove that the two-machine flowshop problem to minimize the maximum completion time (makespan) is NP-hard if job processing times are described by non-decreasing position dependent functions (aging effect) on at least one machine and strongly NP-hard if job processing times are varying on both machines. Furthermore, we construct fast NEH, tabu search with a fast neighborhood search and simulated annealing algorithms that solve the problem with processing times described by arbitrary position dependent functions that model both learning and aging effects. The efficiency of the proposed methods is numerically analyzed.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Agnieszka Rudek, RadosÅaw Rudek,