On a parallel machine scheduling problem with precedence constraints and machine number restrictions

摘要

This paper first presents the identical parallel machine scheduling problem with precedence constraints and machine number restrictions, which mean some jobs must occupy two machines simultaneously. An extension of the largest total amount of successors processing first (LTAP) rule is developed to find near optimal solution of the makespan, and a few lower bounds are computed to evaluate the performance of the proposed algorithm.