Unrelated Parallel Machine Selection and Job Scheduling With the Objective of Minimizing Total Workload and Machine Fixed Costs

This paper is concerned with scheduling of a set of n single-operation tasks/orders on a set of m unrelated parallel machines where subcontracting is allowed. When a machine/subcontractor is chosen to do a set of orders/tasks, it incurs a one-time fixed cost. When a job/order is performed by a machine/subcontractor, there is a cost that depends on the machine/subcontractor. The objective is to choose a subset of k machines and/or subcontractors from the set of all m available machines and/or subcontractors to perform all jobs to minimize the sum of total workload costs and total fixed costs. We discuss the complexity of the problem, and prove NP-hardness of the problem. Simplified mathematical development is provided that allows efficient implementation of two-exchange algorithms. An efficient tabu search heuristic with a diversification generation component is developed. An extensive computational experiment of the heuristic for large-scale problems with comparison to the results from CPLEX software is presented. We also solved 40 benchmark k-median problems available on the Internet that have been used by many researchers.