Depending on the amount of data to process, file generation may take longer.

If it takes too long to generate, you can limit the data by, for example, reducing the range of years.

Article

Download BibTeX

Title

An improved approximation algorithm for a scheduling problem with transporter coordination

Authors

[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ P ] employee

Scientific discipline (Law 2.0)

[2.3] Information and communication technology

Year of publication

2023

Published in

Journal of Scheduling

Journal year: 2023 | Journal volume: vol. 26

Article type

scientific article

Publication language

english

Keywords
EN
  • Approximation algorithm
  • Scheduling
  • Transporter
Abstract

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.

Date of online publication

02.11.2022

Pages (from - to)

559 - 570

DOI

10.1007/s10951-022-00762-6

URL

https://link.springer.com/article/10.1007/s10951-022-00762-6

Ministry points / journal

70

Impact Factor

2 [List 2022]

This website uses cookies to remember the authenticated session of the user. For more information, read about Cookies and Privacy Policy.