Title

A Meta-Raps For The Early/Tardy Single Machine Scheduling Problem

Keywords

Lean manufacturing; Meta-heuristic; Scheduling; Sequence dependent setup times

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.

Publication Date

1-1-2009

Publication Title

International Journal of Production Research

Volume

47

Issue

7

Number of Pages

1717-1732

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1080/00207540701742427

Socpus ID

60749098344 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/60749098344

This document is currently not available here.

Share

COinS