Complexity Results For Scheduling Chains On A Single Machine

Preprint
Publisher Website
Google Scholar
    • preprint
      • Published in RePEc
Abstract
We investigate the computational complexity of deterministic sequencing problems in which unit-time jobs have to be ;.cheduled on a single machine subject to chain-like precedence constraints. NP-hardness is established for the cases in which the number of late jobs or the total weighted tardiness is to be minimized, and for several related problems involving the total weighted completion time criterion.
All Related Versions

This publication has 0 references indexed in Scilit: