An improved approximation algorithm for a scheduling problem with transporter coordination

Yinling Wang; Xin Han; Yong Zhang; Jacek Błażewicz

doi:10.1007/s10951-022-00762-6

Scientific Information System of the Poznań University of Technology

PL EN

Main page / Publications / An improved approximation algorithm for a scheduling problem with transporter coordination

Submit a comment

Article

Download BibTeX

Title

An improved approximation algorithm for a scheduling problem with transporter coordination

Authors

Yinling Wang
Xin Han
Yong Zhang
Jacek Błażewicz (WIiT) ^{[ 1 ][ 2.3 ][ P ]}

^{[ 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

1,4

System created by Poznań University of Technology and Poznan Supercomputing and Networking Center

Log in through eKonto to add to SIS