IE SEMINAR:New FPT Algorithms for the Resource Constrained Scheduling

Speaker:İstenç Tarhan

Title: New FPT Algorithms for the Resource Constrained Scheduling Problems with Time Windows

Date/Time:March 22 2023 1:40 PM

Zoom: https://sabanciuniv.zoom.us/j/93444877042

Abstract:We consider in this paper the resource constrained scheduling problems with time windows. We do not consider a particular objective yet optimize an objective function f with certain properties which are owned by most of the classical scheduling objective functions (e.g., minimization of the makespan, total weighted completion times, total weighted tardiness). This problem is denoted by PS|prec, ri, di|f. We develop two dynamic programming algorithms (DP and DP’) inspired from the Branch-and-Bound algorithms of Mingozzi et al. (1998) and Demeulemeester and Herroelen (1992), respectively. Both DP algorithms, i.e., DP and DP’, build a state graph with n+1 stages where n is the number of jobs. Each path from the last stage to the first one represents a complete feasible schedule. New dominance rules are proposed to be used in the DP algorithms, which are also applicable to most of the scheduling problems with time windows. These rules enable to show that both DP algorithms are fixed-parameter tractable (FPT) with two parameters: i) the pathwidth, which corresponds to the maximum number of overlapping job time windows and ii) the maximum execution time of a job. The proposed DP algorithms are compared with respect to their algorithmic components, the schedules they generate and their time complexities. Computational experiments show that the pathwidth is also a key factor for the practical complexity of the proposed algorithms.

Bio:İstenç Tarhan is a research associate at Sorbonne and Technology of Compiègne Universities. He is also a visiting researcher at Lancaster University CENTRAL Research Center. He completed his Ph.D in Industrial Engineering and Operations Management Department at Koç University. Prior to his current positions, he was a research associate at Lancaster University Management School. His research interests include the development of mathematical models, heuristic and exact approaches for single and multi-objective combinatorial optimization, particularly scheduling, routing and transportation problems. His studies cover both the empirical and theoretical complexity analysis of the developed algorithms.