University of Twente Student Theses


On multi-stage job processing with asymmetric transition costs between operations

Vaish, P. (2022) On multi-stage job processing with asymmetric transition costs between operations.

[img] PDF
Abstract:A facility is a production plant where there are multiple jobs, each consisting of multiple operations. Each of them might require one or multiple other operations to be completed before it. Also, when successive operations are performed on a single machine, there is a transition cost to performing another operation after another. For a single machine facility cost problem, we provide the result that we can use any solver (approximate or exact) that exists for the Asymmetric Travelling Salesperson Problem (ATSP). We also investigate the effect of having when the single machine facility has λ-quasi-metric transition costs and single operation jobs, for which we provide an approximation algorithm which gives a schedule which has a cost at most (1 + λ) away from the cost of the optimal schedule. For the multiple machine facility cost problem, we provide an exact algorithm produced using dynamic programming approach and also show it could be interpreted as a mixed-integer linear program. This approach is extended to produce approximation algorithms using greedy rounding and a naive greedy algorithm, of which one can prove the approximation ratio to scale linearly with the total number of operations. Finally, we show how results derived for single machine facility cost problems could also be used for multiple machines facility cost problem by choosing specific parameters for the cost function.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics, 50 technical science in general, 54 computer science
Programme:Applied Mathematics BSc (56965)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page