Parallel dedicated machines scheduling with chain precedence constraints

Parallel dedicated machines scheduling with chain precedence constraints

0.00 Avg rating0 Votes
Article ID: iaor20124277
Volume: 221
Issue: 2
Start Page Number: 296
End Page Number: 305
Publication Date: Sep 2012
Journal: European Journal of Operational Research
Authors: , , ,
Keywords: scheduling, combinatorial optimization
Abstract:

A set of n nonpreemptive tasks are to be scheduled on m parallel dedicated machines with a regular criterion. Chain precedence constraints among the tasks, deterministic processing times and processing machine of each task are given. We present computational complexity results and solution algorithms for some special cases. When the precedence relations among the tasks are given by two chains, we provide efficient solution algorithms for the minimization of the weighted sum of task completion times and the number of tardy jobs. Moreover, we show that when minimizing the sum of non‐decreasing functions of the completion times of the tasks, a pseudopolynomial time algorithm and a fully polynomial time approximation scheme (FPTAS) exist. Indeed, when the objective is the minimization of the weighted number of tardy jobs or total weighted tardiness the problem is NP‐hard in the ordinary sense. Finally, we consider slightly more general precedence structures and show that, even when the precedence constraints form a comb, makespan minimization problem turns out to be strongly NP‐hard.

Reviews

Required fields are marked *. Your email address will not be published.