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

This paper discusses 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 develop...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2005-08, Vol.32 (8), p.1995-2012
Main Authors: Cao, Dong, Chen, Mingyuan, Wan, Guohua
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Combinatorics
Exact sciences and technology
Heuristic
Machine selection
Operational research and scientific management
Operational research. Management science
Operations research
Optimization
Optimization techniques
Parallel machine scheduling
Scheduling, sequencing
Searches
Studies
Tabu search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper discusses 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.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2004.01.001