A linear programming based method for the resource constrained multi-project scheduling problem with weighted earliness/tardiness costs

Abstract

Çoklu proje ortamlarında firmaların proje havuzlarında zamana bağlı olarak ciddi değişimler olmaktadır. Bu devingen yapı içerisinde, yeni bir projenin havuza dahil olması, mevcut çizelge üzerindeki projelere en az etkiyi yapacak şekilde yeni gelen proje için bir tamamlanma zamanı belirlenmesini zorunlu kılar. Tanımlanan bu problem için geliştirilmiş olan çözüm yöntemi işlik çizelgeleme teknik yazınında sıklıkla kullanılan darboğaz öteleme çözüm yaklaşımının proje çizelgeleme ortamına uyarlanmış halidir. Çözüm yaklaşımın kapsamında, tüm kaynak kısıtlarının gevşetilmesi sonucu oluşan doğrusal model çözülerek öncül bir çizelge elde edilir. Sonraki adımlarda mevcut çizelgedeki kaynak aşımları her kaynak tipi için çözülen erkenlik geçlik yan problemlerinin sonuçlarına bağlı olarak ortadan kaldırılır. Yan problem çözümünde kullanılan erkenlik geçlik katsayıları doğrusal model üzerine uygulanan duyarlılık analizi sonucu elde edilmektedir [1]. Tanıtılan yan problemin çözümü için yöre tarama tabanlı sezgisel bir yöntem geliştirilmiştir. Her yan problem çözümü ana probleme eklenen öncüllük kısıtları yardımıyla, sonraki adımlarda ele alanınan kaynak tipi için kapasite aşımı olmasını önler. Bu şekilde modelin doğrusal yapısı korunurken, diğer kaynak tipleri için duyarlılık analizinin uygulanabilmesi sağlanır. Bu süreç tüm kaynak tipleri etkin hale gelinceye kadar tekrarlanmaktadır. Son olarak, kaynak tiplerinin etkinleştirilme sırasının çözüm yaklaşımının peformansı için önemli bir etken olduğundan, ağaç yapısında tarama ve tekrar çizelgeleme yaklaşımları çözüm yöntemie dahil edilmiştir. Son olarak, sezgisel yerel tarama yöntemi çözüm niceliğinin sınanması amacıyla geliştirilmiştir.1 Kerem Bülbül, Philip Kaminsky. A linear programming based general method for job shop scheduling. 2011, Submitted for publication.

This study addresses the Resource Constrained Multi Project Scheduling Problem with Weighted Earliness Tardiness Costs (RCMPSPWET). In multi-project environments, the project portfolio of a company does often change dramatically in time. In this dynamic context, the arrival of a new project requires quoting a due date while keeping the disruptions to the existing plans and schedules to a minimum. The suggested solution method is an adaptation of the well known shifting bottleneck (SB) heuristic in the job shop literature. Initially, a base schedule is obtained by relaxing all resource capacities and solving the resulting model as a linear program (LP). The SB heuristic then resolves the resource conflicts present in the optimal solution of this resource relaxation iteratively by solving a set of single-resource weighted earliness tardiness scheduling subproblems with precedence constraints. The unit earliness and tardiness costs in the subproblems are estimated by drawing upon tools from LP sensitivity analysis recently proposed by Bülbül et al. [Bülbül et al., 2011] for a general job shop scheduling problem. The subproblems in the SB heuristic are a generalization of the NP-hard single machine weighted earliness tardiness problem, and a neighborhood search based algorithm is applied to these for the efficiency of the overall SB algorithm. The solution of a subproblem introduces new precedence relationships based on the concept of resource flows. These new precedence constraints are incorporated into the LP mentioned above and ensure that the capacity of the resource under consideration is observed. These steps are repeated until all resource conflicts are removed. The order in which the resource conflicts are resolved is a major determinant of the final solution quality, and therefore, a systematic tree search strategy is implemented for resolving the resource conflicts in different orders. A local search algorithm for the original problem is also adopted to benchmark the results.1 Kerem Bülbül, Philip Kaminsky. A linear programming based general method for job shop scheduling. 2011, Submitted for publication.