Order acceptance and scheduling decisions in make-to-order systems

Abstract

Bu tezde, siparişe dayalı üretim yapan sistemlerde eşzamanlı sipariş kabul ve çizelgelemeproblemi ele alınmıştır. Üretim ortamı müşterilerin sipariş verdiği tek makineli bir ortam olarakmodellenmiştir. Bu problemde üreticinin, gelen siparişlerin üretimine başlanabilecek zamanları,işleme sürelerini, termin ve son teslim zamanlarını, dizilime bağlı hazırlık zamanlarını ve her birsiparişin getirebileceği en fazla geliri bildiği varsayılmaktadır. Üretici, bu siparişlerden oluşanhavuzdan belli siparişleri seçip kısıtlı üretim kapasitesini de göz önüne alarak karınıeniyilemelidir. Gecikme, bir siparişten kazanılan gelirin gecikmeyle orantılı olarak azalmasışeklinde cezalandırılmaktadır. Tamamlanma zamanı son teslim tarihini aşan ürünlerden hiç gelirkazanılamamaktadır. Problem, toplam ağırlıklı gecikmenin en küçüklendiği, dizilime bağlıhazırlık zamanları ve sipariş kabul kararları içeren yapısıyla bilinen birçok çizelgelemeprobleminin genel halidir. Problemin bir özel durumu polinom zamanda çözülemeyeceğiispatlanmış (NP-zor) toplam ağırlıklı gecikmenin en küçüklendiği ve dizilime bağlı hazırlıkzamanları içeren çizelgeleme problemidir. Bu nedenle ele aldığımız sipariş kabul ve çizelgeleme(SKÇ) problemi NP-zor'dur. Bu tezde öncelikle SKÇ problemi için karışık tamsayılı doğrusalprogramlama modeli verilmekte ve bu matematiksel model ticari bir çözücü ile çeşitli verisetleri için çözülmektedir. Ayrıca, problemi zorlaştıran faktörler üzerine çıkarımlardabulunulmaktadır. Sonrasında, daha büyük boyutlu problemleri çözebilmek için ISFAN sezgiselalgoritması önerilmektedir. ISFAN algoritmasının performansı problemin eniyilenebildiğidurumlarda en iyi çözümle, diğer durumlarda önerdiğimiz diğer yapısal algoritmalarlakarşılaştırılmaktadır. Problemin en iyi değerini bulamadığımız durumlarda en iyi değere üst sınırolarak karışık tamsayılı doğrusal modelin doğrusal gevşetilmesi ile elde edilen değerlerkullanılmaktadır. Bu üst sınır bazı durumlarda etkili olan geçerli eşitsizliklerle güçlendirilmiştir.Kapsamlı sayısal testlerle, önerilen algoritmaların büyük çaptaki problemler için bile makulhesaplama zamanlarında yüksek kalitede çözümler üretebildiği görülmüştür.

In this thesis, we examine simultaneous order acceptance and scheduling decisions in amake-to-order system. We model the manufacturing environment as a single machineenvironment, with a set of orders coming from customers. In this pool of orders, of which weknow the release dates, due dates, processing times, deadlines, sequence dependent setuptimes and revenues, manufacturer has to decide on the subset of orders to select, consideringthe limited production capacity in order to maximize the profit. The tardiness of orders ispenalized and revenue gained from an order decreases with tardiness, until the deadline, afterwhich no revenue can be obtained. The problem generalizes some well-known schedulingproblems with the objective of minimizing total tardiness and has the sequence dependentsetup times as a further complicating property, as well as the order acceptance decisions. Onespecial case of the problem is total weighted tardiness with sequence dependent setups, whichis proven to be strongly NP-hard. As a result, the OAS problem is strongly NP-hard. In thethesis, first, we give an MILP model for the problem, and solve it with a commercial solverover a range of generated data sets. We draw some conclusions on the factors making theproblem harder. Next, we propose a heuristic algorithm called ISFAN to solve the large-sizeproblems. We compare the performance of the algorithm with respect to the optimal solution,when the problem can be solved optimally, and with several constructive heuristics wedesigned. We use upper bounds generated by LP relaxation of the MILP model forcomparison when optimal objective values are not available. LP relaxation bound isstrengthened with valid inequalities that are effective for some instances. By extensivecomputational tests, the proposed algorithms are found to provide high quality feasiblesolutions, even for large-scale instances, with modest computational effort.