ISSN:
1436-6304
Keywords:
Robot acquisition planning
;
equipment selection
;
mathematical programming
;
heuristic search
;
tabu search
;
simulated annealing
;
Roboter Anschaffungsplanung
;
CIM
;
Bin packing
;
Tabu search
;
Simulated annealing
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Zusammenfassung Dieser Bericht beschreibt die Entwicklung eines mathematischen Programms und dreier effizienter Entscheidungsregeln für die Anschaffungsplanung von Robotern verschiedener Typen für ein CIM-System. In unserem Modell wird eine Kombination von Robotern verschiedener Typen zusammengestellt, die den operationalen Anforderungen (d.h. Zeit und Raum) einer bestimmten Anzahl von Arbeitsplätzen bei gleichzeitig minimalem Kostenaufwand gerecht wird. Im Detail bedeutet das: jeder Roboter zeichnet sich einerseits durch seinen festgesetzten Preis aus und andererseits unterliegt er zwei Kapazitätsbeschränkungen: seiner Maschinenzeit und seiner Arbeitsfläche; jeder Arbeitsplatz stellt bestimmte Anforderungen, die uns bekannt sind, sowohl an die Maschinenzeit als auch an die Arbeitsfläche und soll von nur einem Roboter bedient werden. Das Modell wird durch ein mathematisches 0–1-Programm dargestellt und hat sich als schwieriger als das bekannte NP-schwere zweidimensionale Bin Packing-Problem herausgestellt. Die drei entwickelten Entscheidungsregeln sind: ‘greedy heuristic’, ‘tabu thresholding’ und ‘simulated annealing’. Alle Entscheidungsregeln wurden anhand 450 zufällig generierter Problemfälle getestet. Die Computerergebnisse deuten darauf hin, daß alle Algorithmen für die Lösung von Problemen praktischer Größen (d.h. 50 Arbeitsplätze und maximal 20 Roboter) anwendbar und ausreichend sind. Hinsichtlich der zeitlichen Dauer und Qualität der Problemlösung hebt sich jedoch keine der Entscheidungsregeln wesentlich von den anderen beiden ab. Zukünftige Forschungsaspekte werden ebenfalls aufgeführt.
Notes:
Abstract In this paper, a planning model and three efficient heuristics are developed for equipment acquisition planning for a CIM system using multiple-type robots. Our planning model considers selection of a proper mix of multiple-type robots such that operational requirements (i.e., time and space) from a given number of work stations are satisfied at minimal system cost. In specific, each robot is characterized by its fixed charge and subject to two capacity constraints on machine time and work space; and each work station has known demands for both machine time and work space, and is to be served by only one robot. The model is formulated as a pure 0–1 mathematical program and is shown to be harder than two-dimensional bin packing, a well-known NP-hard problem. The three heuristics developed are: a greedy heuristic, tabu thresholding, and simulated annealing. All heuristics are tested by solving 450 randomly generated problems. Computational results indicate that all three heuristics are effective and efficient in solving problems of a practical size (i.e., 50 work stations and a maximum of 20 robots). However, none of the heuristics are overwhelmingly better than the others in terms of both solution time and quality. Future research issues are also discussed.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01719252
Permalink
