Backtracking and its amoebic properties in one-dimensional machine location problems

Backtracking and its amoebic properties in one-dimensional machine location problems

0.00 Avg rating0 Votes
Article ID: iaor19951237
Country: United Kingdom
Volume: 45
Issue: 9
Start Page Number: 1024
End Page Number: 1039
Publication Date: Sep 1994
Journal: Journal of the Operational Research Society
Authors: , ,
Keywords: production
Abstract:

This paper studies the assignment of M unique machines to M equally spaced locations along a linear material handling track with the objective of minimizing the cost of (jobs) backtracking (i.e. moving upstream). Because of the arrangement of machines and restrictions imposed by the sequence of operations for each job, some jobs may have to backtrack to complete required processing on different machines. This problem is formulated as a quadratic assignment problem. An optimal solution to a problem with large M is computationally intractable. The backtracking distance matrix in problems involving equally-spaced machine locations in one dimension is seen to possess some unique characteristics called amoebic properties. Ten amoebic properties have been identified and exploited to devise a heuristic and a lower bound on the optimal solution. Results which describe the performance of the heuristic and the lower bound are presented.

Reviews

Required fields are marked *. Your email address will not be published.