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.
|
PDF
1MB |
| 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: | https://purl.utwente.nl/essays/92650 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page