Research Reports from the Department of Operations
Document Type
Dissertation
Publication Date
6-1-1975
Abstract
This dissertation deals with finding an optimal way of changing a given arrangement to a (specified) new arrangement. Two types of problems are considered. In the first type of problem, there is no extra storage space available for storage of the objects. The rearrangement is done by a sequence of pairwise exchanges. In the second type of problem there is extra storage space available for storage. The rearrangement in this case is done by a vehicle which moves one object at a time. Problems are further classified by type of arrangement as basic cycles, cycles--and general arrangement- and by the constraints such as linearity and minimality constraints. For each problem a cost d structure is defined. Polynomial algorithms have been developed for a few problems of Type I under certain cost structures. A characterization of all the feasible sequences for the basic cycle problems with minimality constraint is developed. Two algorithms,. one a dynamic programming and the other a branch and bound type, are proposed to solve this problem. A polynomial algorithm is described for the Type II problems with minimality constraint and it is shown that for this problem the sequence of moves is specified by the first move. The cycle problem with object dependent cost has been solved efficiently.
Keywords
Operations research, Algorithms, Mathematical optimization, Dynamic programming, Branch and bound algorithms, Inventory control
Publication Title
Dissertation/Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 364 ; Submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy.
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Mittal, Ashok Kumar, "Optimal Rearrangement of Objects" (1975). Research Reports from the Department of Operations. 396.
https://commons.case.edu/wsom-ops-reports/396