Bi-criteria Scheduling with Machine Assignment Costs

Abstract

We consider parallel machine scheduling problems where the processing of the jobs on the machines involves two types of costs. The first type of cost is similar to one of two classical objective functions that are often considered in scheduling theory; it is either the total completion time or the makespan. The second type of cost involves an actual cost associated with the processing of a specific job on a given machine. Each job-machine combination may have a different cost. The optimization problems considered may be structured in several different ways. We consider first the two objectives hierarchically; that is, first one objective is being optimized and the class of optimal solutions is determined, and then the second objective is optimized among all schedules that are optimal with respect to the first objective. Another structure that is considered involves the minimization of a linear combination of the two objective functions. We present an overview of the computational complexities of all the problems considered in our framework. (C) 2012 Elsevier B.V. All rights reserved.