Selecting jobs for a heavily loaded shop with lateness penalties

One way of adjusting the workload in a manufacturing facility when available jobs exceed current capacity is to select a subset of jobs with the objective of maximizing total net profit for the firm, that is, revenue contributed by jobs processed less a penalty for lateness. This motivates us to formulate the objective function in terms of revenues minus costs, in order to reflect the trade-offs faced by the firm itself, which views costs mainly in the context of the reduction of its profits. The authors present a model that uses weighted lateness as a criterion for time-related penalties. Taking advantage of two special characteristics of the problem, they develop an optimal algorithm and two heuristic procedures. Computational results show that the myopic heuristic demonstrates near-optimal performance in a fraction of the processing time of the optimal benchmark.