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:
Filename Description Size
Efficient Lagrangian Heuristics - Gu et al.pdfPublished version295.17 kB
Adobe PDF
Full metadata record
© 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: