Revenue Maximization on Parallel Machines

Summary Revenue management is essentially the process of allocating resources to the right customer at the right time and the right price (cf. [9]). A slightly different approach to revenue maximization can be met in “classical” scheduling theory (cf. [3]), where the goal is to maximize the criterion value, i.e. the profit, for some given values of the problem parameters (cf. [8]). Such a model finds many practical applications. For example, a set of jobs can represent a set of customer orders which may give certain profit to a producer. Due to limited resources, modeled by a machine or a set of machines, the producer has to decide whether to accept or reject a particular order and how to schedule accepted orders in the system. Delays in the completions of orders cause penalties, which decrease the total revenue obtained from the realized orders. For this reason, maximizing revenue is strictly related to due date involving criteria (cf. [3]) such as minimizing tardiness or late work (cf. [11]). The maximum revenue objective function has been studied mostly for the single machine environment (cf. [2], [5], [8], [10]). In our research, we investigate the problem of selecting and executing jobs on identical parallel machines in order to maximize the total revenue (profit) with the weighted tardiness penalty.