Single machine scheduling to minimize the number of late jobs under uncertainty
In this paper, we deal with the problem of sequencing a finite number of jobs for processing by a single machine with the objective of minimizing the number of jobs that are not completed by their due dates. We propose a rather general model based on an algebraic approach. By specifying suitable binary relations between due dates, between processing times, and between due dates and job completion times, a number of well-known results for deterministic, stochastic, and fuzzy environments can be obtained as special cases of presented general results. We show that in this general setting, variants of Jackson's lemma are valid and optimal sequences can be obtained by modifications of Moore's algorithm for a wide range of binary relations and a wide range of types of job completion times. (C) 2002 Elsevier B.V. All rights reserved.
single machine scheduling number of late jobs combinatorial problems