Efficient Lagrangian heuristics for the two-stage flow shop with job dependent buffer requirements
- Publication Type:
- Journal Article
- Journal of Discrete Algorithms, 2018, 52-53 pp. 143 - 155
- Issue Date:
Files in This Item:
|Efficient lagrangian heuristics for the two-stage flow shop.pdf||Accepted Manuscript Version||2.05 MB|
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is being processed and is not currently available.
© 2018 Elsevier B.V. The paper is concerned with minimisation of the total weighted completion time for the two-stage flow shop with a buffer. In contrast to the vast literature on this topic, the buffer requirement varies from job to job and a job occupies the buffer continuously from the start of its first operation till the completion of its second operation rather than only between operations. Such problems arise in supply chains requiring unloading and loading of minerals and in some multimedia systems. The problem is NP-hard in the strong sense, and we prove that if the order of jobs is fixed for one of the stages, then even for the criteria of the maximum completion time or the total completion time the problem remains NP-hard in the strong sense. Straightforward integer programming approach is impossible even for modest problem sizes. The paper presents a Lagrangian relaxation based decomposition approach that allows to use for each problem, obtained by this decomposition, a very fast algorithm. Several Lagrangian heuristics are evaluated by means of computational experiments.
Please use this identifier to cite or link to this item: