Title

A Meta-RaPS for the early/tardy single machine scheduling problem

Authors

Authors

S. Hepdogan; R. Moraga; G. W. DePuy;G. E. Whitehouse

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abstract

This paper investigates a meta-heuristic solution approach to the early/tardy single machine scheduling problem with common due date and sequence-dependent setup times. The objective of this problem is to minimise the total amount of earliness and tardiness of jobs that are assigned to a single machine. The popularity of just-in-time (JIT) and lean manufacturing scheduling approaches makes the minimisation of earliness and tardiness important and relevant. In this research the early/tardy problem is solved by Meta-RaPS (meta-heuristic for randomised priority search). Meta-RaPS is an iterative meta-heuristic which is a generic, high level strategy used to modify greedy algorithms based on the insertion of a random element. In this case a greedy heuristic, the shortest adjusted processing time, is modified by Meta-RaPS and the good solutions are improved by a local search algorithm. A comparison with the existing ETP solution procedures using well-known test problems shows Meta-RaPS produces better solutions in terms of percent difference from optimal. The results provide high quality solutions in reasonable computation time, demonstrating the effectiveness of the simple and practical framework of Meta-RaPS.

Journal Title

International Journal of Production Research

Volume

47

Issue/Number

7

Publication Date

1-1-2009

Document Type

Article

First Page

1717

Last Page

1732

WOS Identifier

WOS:000263266500001

ISSN

0020-7543

Share

COinS