Parallel machine scheduling problems considering regular measures of performance and machine cost

Abstract

This research considers a broad range of scheduling problems in the parallel machines environment. Schedules are evaluated according to two independent components of the objective function: (1) machine cost consisting of a fixed cost and a variable cost; and (2) a regular measure of performance. This study is only one of a few that take the selection of machines among those available as a decision variable. For machine cost with concave functions, we derive the general characteristics of optimal solutions with respect to decisions on the number of machines to use and the way to load the machines. Our analysis is not restricted to the machine cost criterion, but may be extended to other measures with concave functions. Furthermore, we provide a Pareto efficient perspective in understanding the tradeoff between machine cost and any regular measure of performance.

Keywords:

• scheduling
• multi-objective criteria
• parallel machines
• machine utilization
• Pareto Solutions