Scheduling of uniform parallel machines with s-precedence constraints

This paper considers a problem of scheduling s-precedence constrained jobs on machines in parallel which have different speeds. The objective is to minimize the weighted total completion time. The s-precedence relation between two jobs ii and jj represents the situation where job jj is constrained from processing until job ii starts processing, which is different from the standard definition of a precedence relation where jj cannot start until ii completes. An LP-based heuristic procedure is derived for the problem. Numerical experiments are conducted to show that the derived heuristic finds effective solutions.