An improved approximation algorithm for a scheduling problem with transporter coordination
[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ P ] pracownik
2023
artykuł naukowy
angielski
- Approximation algorithm
- Scheduling
- Transporter
EN We study the following scheduling problem with transportation. Given a set of n jobs that need to be processed on a single machine, we need to deliver the finished jobs to one of the two destinations using a single transporter. The goal is to minimize the time that all the jobs are delivered to their destination, such that the transporter returns. We propose a 11/6+ε-approximation algorithm which improves upon the best-known approximation ratio of 2.
02.11.2022
559 - 570
70
2 [Lista 2022]