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 (DP1 and DP2) inspired from the Branch-and-Bound algorithms of Mingozzi et al. (1998) and Demeulemeester and Herroelen (1992), respectively. Both DP algorithms, i.e. DP1 and DP2, 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. We show that the DP1 algorithm generates all and only active schedules whereas the DP2 algorithm generates all and only semi-active schedules. 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. 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.
