University of Twente Student Theses
As of Friday, 8 August 2025, the current Student Theses repository is no longer available for thesis uploads. A new Student Theses repository will be available starting Friday, 15 August 2025.
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