Exact approaches for the no wait flowshop problem

Abstract

Bu çalışmada, permütasyon akış tipi üretimin bir çeşidi olan beklemesiz akış tipi üretim incelenmiştir. Beklemesiz akış tipi üretimlerde, bir işin işlenmesi başladıysa o ürün gecikmeye ve kesintiye uğrayamaz. Bu çizelgeleme modeli genelde bir biri ardına gelen proseslerin görüldüğü yerlerde kullanılır. Ürün üretim süresinin en aza indirilmesi amaçlanan beklemesiz akış tipi üretim problemi NP-hard'dır. Bu sebeple, birçok araştırmacı optimal çözüm bulmak yerine, daha makul zamanlarda optimal çözüme yakın çözümler üreten sezgisel çözümlere yönelmişlerdir. Sunulan yöntem ise n tane iş ve m tane makinenin olduğu beklemesiz akış tipi üretimlerin, ürün üretim süresini en aza indirecek olan kesin çözümü vermektedir. Bu yöntem, tembel kısıtlama tekniklerini kullanmaktadır. Ayrıca optimale yakın çözüm üreten bir sezgisel yöntem sunulmuştur. Bu sezgisel yöntem, beklemesiz akış tipi probleminin asimetrik gezgin satıcı problemine dönüştürülerek, çözüm esnasında oluşan döngüleri, zincir kırma yöntemiyle yok etmeye dayanmaktadır.

In this study, no wait flow shop problem, which is a variant of permutation flow shop, is investigated. In a no wait flow shop, after processing of a job is started, it must be processed completely without any delay or cut-off. This scheduling model is generally used where operations are compulsory to follow one right way after the other due. No wait flow shop problem with objective of minimizing makespan is NP-hard, therefore researchers mostly study heuristic approaches, which give near optimal solutions, because of their ease of implementation. Proposed solution generates exact solution for the n jobs and m machines no wait flow shop systems with objective of minimizing makespan in competitive times. It uses adding lazy constraints technique. In additionally, a new heuristic is proposed. This heuristic find near optimal solution and uses chain injection method.