SCHEDULING TO MINIMIZE THE TOTAL COMPRESSION AND LATE COSTS

We consider a single-machine scheduling model in which the job process ing times are controllable variables with linear costs. The objective is to minimize the sum of the cost incurred in compressing job process ing times and the cost associated with the number of late jobs. The pr oblem is shown to be NP-hard even when the due dates of all jobs are i dentical. We present a dynamic programming solution algorithm and a fu lly polynomial approximation scheme for the problem. Several efficient heuristics are proposed for solving the problem. Computational experi ments demonstrate that the heuristics are capable of producing near-op timal solutions quickly. (C) 1998 John Wiley & Sons, Inc.