Title

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

Document Type

Article

Publication Title

IEEE Transactions on Automation Science and Engineering

Abstract

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. Note to Practitioners - To be competitive in the global market, companies must be prudent in the use of their resources. This paper considers a parallel scheduling environment where choosing in-house machines and/or subcontractors as resources to perform the orders/jobs is the main objective. Processing time (or cost) of a job to be performed by different machines or subcontractors can be different. Furthermore, if a machine or a subcontractor is chosen to perform a set of orders, there is a one-time fixed cost (in the case of subcontractor it can be considered transportation cost) that depends on the machine or subcontractor. The scheduling criteria are to choose a subset of k machines and/or subcontractors to do all orders/jobs while minimizing the sum of the total workload and total fixed costs. The complexity of the problem is discussed and shown to be NP-hard. An efficient tabu search that solves large-scale problems in fraction of a second of CPU time is presented and an extensive computational experiment is provided.

First Page

1955

Last Page

1963

DOI

10.1109/TASE.2018.2832440

Publication Date

10-1-2018

This document is currently not available here.

Share

COinS