Time/cost trade-offs in machine scheduling with controllable processing times

Abstract

Kontrol edilebilir işlem süreleri çizelgeleme kararları verilirken dikkate alınmasıgereken önemli bir özelliktir. Çünkü pek çok endüstri uygulaması, işlemsürelerinin kontrol edilebilmesine olanak sağlamaktadır. Buna en iyi bilinen örnek bilgisayar sayısal kontrollü (CNC) kesme makineleridir. Verilen bir iş kümesi içinseçilen işlem süreleri toplam üretim maliyetini belirlediği gibi çizelgeleme performansını da önemli bir şekilde etkiler. Bu yüzden işlem süreleri ve çizelgeleme kararlarını birlikte verirken hem toplam üretim maliyeti hem de çizelgeleme performans hedeerini birlikte eniyilemek gerekir. Bu tezde, tek makine, paralel makine gibi değişik çizelgeleme ortamlarında bu çift hedei problemler üzerinde çalıştık. Toplam iş bitim süresi ve maksimum iş bitim süresi gibi çizelgeleme performans kriterlerini ele aldık. Çalışmada özellikle CNC torna işlemleri için bilinen konveks maliyet fonksiyonunu kullandık. Ele aldığımız her problem için etkin çözüm bulmaya yarayan hızlı metodlar önerdik. Çalışmamızda özellikle tek hedei problemler çözerek etkin çözüm bulmaya çalıştık. Bu yönteme literatürde epsilon-kısıt yaklaşımı denmektedir. Biz de bu çalışmada etkin problem formülasyonları önerdik ve bu formülasyonlar üzerinde gösterdiğimiz özellikleri kullanarak yaklaşık etkin çözümler üreten sezgisel metodlar geliştirdik.Bu tezde, bir başka yaklaşımla, kontrol edilebilir işlem süreleriyle iş-makineatama problemi için yeni bir konik karesel formülasyon önerdik. Bu kısımda heriş için konveks bir sıkıştırma maliyeti fonksiyonu ele aldık ve kar maksimizasyonproblemi çözdük. Problemin çözümünü zorlaştıran temel nedenlerden biri maliyetfonksiyonunun konveks olmasıdır. Önerdiğimiz güçlendirilmiş formülasyonla buzorluğu ortadan kaldırdık. Yaklaşımımız, ayrık konveks maliyet fonksiyonlarıiçeren başka karışık 0-1 eniyileme problemlerinde de kullanılabilecek genel biryaklaşımdır. Deneysel hesaplamalarımız önerdiğimiz formülasyonun iş-makine atama problemlerinin eniyi çözümünde çok etkili olduğunu gösterdi.Son olarak bu tezde, kontrol edilebilir işlem süreleriyle yeniden çizelgelemeüzerine çalıştık. Sabit işlem süreleriyle yeniden çizelgelemeden farklı olarak kontrol edilebilir işlem sürelerinin makine bozulması gibi aksaklıklar karşısında çok farklı alternatif çözümler üretmemize olanak sağladığını gösterdik. Farklı paralel makineler üzerinde konveks sıkıştırma maliyet fonksiyonu varlığında makinelerden birinin bir süre çalışamaması durumunda yeniden çizelgeleme problemi üzerinde çalıştık. Yeniden çizelgelemede amaç iş-makine atamalarını yeniden yaparak ve işlem sürelerini değiştirerek eski çizelgeyi en kşa zamanda yakalamaktır. Öte yandan toplam üretim maliyetini de enazlamak gerekir. Çelişen bu iki hedefi ele alan alternatif yeniden çizelgeleme problemleri önerdik. Bu problemleri güçlendirilmiş konik formülasyon yaklaşımını kullanarak çözdük. Ayrıca hızlı sezgisel tarama algoritmaları önerdik.

Processing time controllability is a critical aspect in scheduling decisionssince most of the scheduling practice in industry allows controlling processingtimes. A very well known example is the computer numerically controlled (CNC)machines in flexible manufacturing systems. Selected processing times for agiven set of jobs determine the manufacturing cost of the jobs and stronglyaffect their scheduling performance. Hence, when making processing time andscheduling decisions at the same time, one must consider both the manufacturingcost and the scheduling performance objectives.In this thesis, we have studiedsuch bicriteria scheduling problems in various scheduling environmentsincludingsingle, parallel and non-identical parallel machine environments. We haveincluded some regular scheduling performance measures such as total weightedcompletion time and makespan. We have considered the convexmanufacturing cost function of CNC turning operation.We have provided alternative methods to find efficient solutions in eachproblem. We have particularly focused on the single objective problems to getefficient solutions, called the $/epsilon$-constraintapproach. We have provided efficientformulations for the problems and shown useful properties which led us todevelop fast heuristics to generate set of efficient solutions.In this thesis, taking another point of view, we have also studied a conicquadratic reformulation of a machine-job assignment problem with controllableprocessing times. We have considered a convex compression cost function foreach job and solved a profit maximization problem. The convexity of costfunctions is a major source of difficulty in finding optimal integer solutionsin this problem, but our strengthened conic reformulation has eliminated thisdifficulty. Our reformulation approach is sufficiently general so that it canalso be applied to other mixed 0-1 optimization problems with separable convexcost functions. Our computational results demonstrate that the proposed conicreformulation is very effective for solving the machine-job assignment problemwith controllable processing times to optimality.Finally, in this thesis, we have considered rescheduling with controllableprocessing times. In particular, we show that in contrast to fixed processingtimes, if we have the flexibility to control the processing times of the jobs,we can generate alternative reactive schedules in response to a disruptionsuch as machine breakdown. We consider a non-identical parallel machiningenvironment where processing times of the jobs are compressible at a certaincost which is a convex function of the compression on the processing time.When rescheduling, it is critical to catch up the initial schedule as soon aspossible by reassigning the jobs to the machines and changing their processingtimes. On the other hand, one must keep the total cost of the jobs at minimum.We present alternative match-up scheduling problems dealing with thistrade-off. We use the strong conic reformulation approach insolving these problems. We further provide fast heuristic algorithms.