Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem

AbstractThis paper considers the problem of minimizing the weighted number of late jobs in the two-machine job-shop with unit time operations. We show its NP-hardness and propose an O(n5∑wi) time algorithm, which is based on solving optimally a related problem where a maximal set of early jobs is to be determined