A unified view of parallel machine scheduling with interdependent processing rates

In this paper, we are concerned with the problem of scheduling n jobs on m machines. The job processing rate is interdependent and the jobs are non-preemptive. During the last several decades, a number of related models for parallel machine scheduling with interdependent processing rates (PMS-IPR) have appeared in the scheduling literature. Some of these models have been studied independently from one another. The purpose of this paper is to present two general PMS-IPR models that capture the essence of many of these existing PMS-IPR models. Several new complexity results are presented. We discuss improvements on some existing models. Furthermore, for an extension of the two related PMS-IPR models where they include many resource constraint models with controllable processing times, we propose an efficient dynamic programming procedure that solves the problem to optimality.