SELECTING JOBS FOR A HEAVILY LOADED SHOP WITH LATENESS PENALTIES

One way of adjusting the workload in a manufacturing facility when ava ilable jobs exceed current capacity is to select a subset of jobs with the objective of maximizing total net profit for the firm, that is, r evenue 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 its elf, which views costs mainly in the context of the reduction of its p rofits. We present a model that uses weighted lateness as a criterion for time-related penalties. Taking advantage of two special characteri stics of the problem, we develop an optimal algorithm and two heuristi c procedures. Computational results show that the myopic heuristic dem onstrates near-optimal performance in a fraction of the processing tim e of the optimal benchmark.