Parallel Machine Selection and Job Scheduling to Minimize Sum of Machine Holding Cost, Total Machine Time Costs, and Total Tardiness Costs

This paper is concerned with scheduling of a set of single-operation tasks on a set of parallel machines where subcontracting is allowed. The objective is to choose a subset of machines/subcontractors from a set of available machines/subcontractors to perform all jobs to minimize sum of several costs. Processing time of jobs is assumed to be equal. Lower and upper bound for number of jobs assigned to a machine/subcontractor is considered. We first present a comprehensive survey of applications and models. We show special case of the problem when lower bound for number of jobs assigned to each machine/subcontractor is equal to zero is equivalent to single-sink fixed-charge transportation problem (SSFCT). This proves NP-hardness of the problem. Efficient dynamic programming algorithm for this special case is presented. Complicating issues regarding the general case with nonzero lower bounds for number of jobs assigned to machines/subcontractors is discussed. We transfer the general problem to multiple choice knapsack problem (MCKP) that can be solved efficiently using available algorithms. Several new problems are introduced. Complexity of each problem is resolved. Transformation to MCKP is provided that allows available algorithms to solve the problems. The main contribution of this paper is to establish theoretical results regarding the solution of these difficult problems.