Mathematical models and heuristic algorithms for a multi-product lot streaming problem in a two-machine flowshop

Abstract

In this study, we consider a multi-product lot streaming problem to minimize the makespan on a two-machine flowshop environment in which all product lots are processed by Machine 1 and then by Machine 2. Most of the current studies in the literature of the multi-product lot streaming problem assume that the number of sublots for each product is known in advance, and determines the size for each sublot of every product and the sequence of sublots of all products. However, in our study we assume that the total number of sublots for all products is known advance, although the number of sublots for each product is not known in advance. Our problem is to determine the number of sublots for each product, the size of each sublot and the sequence of sublots that gives the minimum makespan. We investigate this multi-product lot streaming problem for two cases in which sublots of each product are equal sized in the first case while sublots of each product are unequal sized in the second case. We develop mixed integer linear mathematical models and heuristic algorithms for solving each case. We compare these solutions of mathematical models and heuristic algorithm. We design computational experiments to evaluate the performance of our solutions approaches in terms of makespan time. The results show that the mixed integer programming models do not seem to be a useful alternative, especially for large scale problem instances. However, our proposed heuristic algorithms find optimal or near-optimal solutions in very short time

Bu çalışmada, tüm ürünlerin önce birinci ve daha sonra ikinci makinede işlem gördüğü iki makinalı bir akış tipi üretim sisteminde tüm ürün kafilelerinin bitirilme süresini en küçükleyen çok ürünlü kafile bölme ve kaydırma problemi ele alınmıştır. Çok ürünlü kafile bölme ve kaydırma problemi literatüründe yer alan çalışmaların çoğu, her ürün kafilesinde yer alan alt kafilelerin sayısının önceden bilindiğini varsayar ve her ürüne ait alt kafilelerin büyüklüğü ile tüm kafilelere ait alt kafilelerin kendi aralarındaki işlem sırasını belirler. Oysa ki, yaptığımız çalışmada, her ürün kafilesinde yer alan alt kafilelerin sayısının önceden bilinmemesine karşın tüm ürün kafilelerinde yer alan alt kafilelerin toplam sayısının önceden bilindiğini varsaymaktayız. Sorunumuz, her ürün kafilesinde yer alacak alt kafilelerin sayısını, bu alt kafilelerin büyüklüğünü ve tüm ürün kafilerinin bitirilme süresini en küçükleyecek şekilde tüm kafilelere ait alt kafilelerin kendi aralarındaki işlem sırasını belirlemektir. Bu çok ürünlü kafile bölme ve kaydırma problemini iki farklı durum için irdeledik. Birinci durumda her ürün kafilesindeki alt kafileler eşit büyüklükteyken, ikinci durumda her ürün kafilesindeki alt kafileler eşit olmayan büyüklükte olabilmektedir. Çözüm yaklaşımlarımızın hem çözüm kalitesi hem de süresi açısından performansını değerlendirmek için sayısal deneyler tasarladık. Sonuçlar, karışık tam sayılı programlama modellerinin özellikle büyük ölçekli problem örnekleri için yararlı bir alternatif olmadığını göstermiştir. Bununla birlikte, önerdiğimiz sezgisel algoritmalar çok kısa sürede optimum veya optimuma yakın çözümler bulmaktadır.