Article ID: | iaor19981167 |
Country: | United Kingdom |
Volume: | 35 |
Issue: | 7 |
Start Page Number: | 1807 |
End Page Number: | 1823 |
Publication Date: | Jul 1997 |
Journal: | International Journal of Production Research |
Authors: | Brandimarte P., Alfier A. |
Keywords: | job shop |
Manufacturing systems are often characterized by the use of resources which need to be ‘renewed’ after a period of use, such as tools and dies. The resources are not available during their maintenance and if it is too expensive to purchase a suitable number of copies, this may introduce delays and lower the quality of the schedule. We refer to such resources as delay-renewable. In the paper we consider a two-fold generalization of the classical job shop scheduling problem: the operations require the concurrent use of different resources (not only one machine) and the resources are delay-renewable. The resulting scheduling problem is obviously rather difficult and calls for suitable heuristics. A natural way to devise a heuristic approach is to decompose the overall problem into sub-problems and to exploit high-quality meta-heuristics, such as tabu search, for their solution. The purpose of the paper is to discuss and compare two decomposition approaches, differing in the way sub-problems interact, i.e. through constraints and/or information.