Parallel machine selection and job scheduling to minimize machine cost and job tardiness

This paper discussed the problem of simultaneously selecting and scheduling parallel machines to minimize the sum of machine holding cost and job tardiness cost. A combinatorial optimization model is developed for this purpose. Solving the developed model is NP-hard. A heuristic algorithm is developed to locate the optimal or near-optimal solutions based on a Tabu search mechanism specially designed to control the search process in the solution neighborhood for jobs scheduled on specific machines. Numerical examples show that the solutions of the model lead to compromises between the system cost related to machine selection and the operational cost related to job tardiness penalties. The examples also show that the developed algorithm is effective and computationally efficient.