Efficient lagrangian heuristics for the two-stage flow shop with job dependent buffer requirements
- Publication Type:
- Conference Proceeding
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2018, 10765 LNCS pp. 312 - 324
- Issue Date:
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© Springer International Publishing AG, part of Springer Nature 2018. The paper is concerned with minimisation of 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 and the 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: