An online algorithm for the glass cutting problem with defects of multiple grades and products with quality classes

Abstract

Bu tez çalışmasında, çeşitli hata noktaları içeren düz bir cam şeritten kesilecek ürünlerin cam üzerine yerleştirilmesi problemine odaklanmaktayız. Düz cam üretiminde, üretim hattı üzerinde sürekli olarak akmakta olan cam şeritten, farklı boyutlarda ve farklı kalite sınıflarında cam ürünleri kesilir. Kalite sınıfları, bir ürün üzerinde her hata türünden en çok kaç adet hatanın tolere edilebileceğini gösterir. Ait olduğu kalite sınıfının kalite gereksinimlerini yerine getirmeyen ürünler artık cam olarak kabul edilir ve geri dönüştürülmek üzere fırına yollanır. Sürekli bir cam üretim hattında, kesilecek ürünlere karar verme işlemi gerçek zamanlı olarak yapıldığından karar verme süresi kısıtlıdır. Bu problemin temel amacı, sınırlı bir süre içinde cam şeridinden kesilecek ürünlerin yerleşimini toplam artık cam alanını en aza indirecek şekilde belirlemektir. Siparişlerin zamanında teslim edilebilmesi için kesilecek ürünlere karar verirken her ürün türünün günlük üretim hedefleri de göz önünde bulundurulur. Bu gerçek zamanlı problemin çözümü için, kayan ufuk üzerinde bir dizi statik kesim problemini kesin ya da yaklaşık yöntemlerle çözerek, her statik çözümün sadece ilk birkaç kesimini uygulayan bir çevrim içi algoritma önerilmektedir. Bu çalışmada sabit uzunlukta ve hatalar içeren bir cam şeridi üzerindeki statik kesim problemini çözmek için Genetik Programlama (GP), Dinamik Programlama (DP) ve Karışık Tamsayılı Programlama (KTP) yöntemleri geliştirildi. Bu yöntemler gerçek zamanlı çözüm algoritmasına entegre edilerek, farklı hata yoğunlukları içeren gerçekçi üretim örnekleri üzerinde test edildi. Algoritmanın ilk versiyonlarında üretim hedefleri birer kısıt olarak dikkate alındı. Sonraki versiyonlarda ise üretimin daha dengeli yapılmasını sağlayarak sonuçların kalitesini artırmak amacıyla üretim hedefleri amaç fonksiyonuna eklendi. Bununla birlikte, gerçek zamanlı algoritmanın değişen üretim koşullarına uyum sağlayabilen adaptif bir uyarlaması da çalışmaya dahil edildi. Bu tez farklı hata türleri ve ürün kalite sınıfları içeren gerçek zamanlı bir kesim probleminin çözümünü içeren ilk çalışmalardan biridir.

In this thesis, we focus on the problem of placing cutting patterns on a sheet of flat glass that contains various types of defects. In flat glass production, a continuous glass sheet is cut into glass products of different sizes and different quality classes. Each quality class indicates the maximum number of defects of each type that can be tolerated on a glass product. Products that do not meet the quality requirements defined by their quality classes are considered scrap and sent back to the furnace to be recycled. In a continuous glass production line, patterns to be cut from the glass sheet have to be determined in real time, which limits the time available for decision making. The main goal of the glass cutting problem is to determine the cutting patterns in a limited time so as to minimize the total area of scrap glass. In selecting the products to be cut, daily production targets of each product type are also considered to ensure timely delivery of orders. To solve this real time glass cutting problem, we propose an online algorithm that solves a series of static cutting problems over a rolling horizon using various approaches and implements the first few cuts from each static solution to avoid a myopic decision.In this study, we develop genetic algorithm (GA), dynamic programming (DP) and Mixed Integer Programming (MIP) based methods for solving the static cutting problem on a glass sheet of fixed size that contains defects. These methods are integrated into the online algorithm and tested using realistic instances with different defect densities. In the initial versions of the algorithm, production targets are used as constraints. Later, production targets are integrated into the objective function in order to the improve solution quality by balancing the production of different products during the production run. Moreover, an adaptive version of the algorithm, which is capable of adjusting itself based on the current status of the production run, is also provided in this study. This thesis is one of the first studies in the literature that solves a real time cutting problem with defects of multiple grades and products with quality classes.