Standard

On the two-machine routing open shop on a tree with preemption allowed. / Agzyamova, P. M.; Chernykh, I. D.

In: Siberian Electronic Mathematical Reports, Vol. 19, No. 2, 2022, p. 548-561.

Research output: Contribution to journalArticlepeer-review

Harvard

Agzyamova, PM & Chernykh, ID 2022, 'On the two-machine routing open shop on a tree with preemption allowed', Siberian Electronic Mathematical Reports, vol. 19, no. 2, pp. 548-561. https://doi.org/10.33048/semi.2022.19.046

APA

Vancouver

Agzyamova PM, Chernykh ID. On the two-machine routing open shop on a tree with preemption allowed. Siberian Electronic Mathematical Reports. 2022;19(2):548-561. doi: 10.33048/semi.2022.19.046

Author

Agzyamova, P. M. ; Chernykh, I. D. / On the two-machine routing open shop on a tree with preemption allowed. In: Siberian Electronic Mathematical Reports. 2022 ; Vol. 19, No. 2. pp. 548-561.

BibTeX

@article{379fe3949d0746c09a01239b7b67a4ba,
title = "On the two-machine routing open shop on a tree with preemption allowed",
abstract = "The routing open shop problem is a natural generalization of the metric TSP and a classical open shop scheduling problem. Jobs are located at the nodes of a given transportation network, and mobile machines have to perform operations on those jobs while traveling over the edges. Machines are obligated to return to the initial location after completing all operations. The goal is to minimize the makespan. We consider the two-machine routing open shop on a tree with preemption in a general setting, where travel times are machine and direction-dependent. For this problem we describe a wide polynomially solvable special case, for which the optimal makespan is guaranteed to coincide with the standard lower bound.",
keywords = "Asymmetric transportation network, Individual travel times, Polynomially solvable cases, Restricted preemption, Routing open shop, Shop scheduling, Standard lower bound",
author = "Agzyamova, {P. M.} and Chernykh, {I. D.}",
note = "Funding Information: Agzyamova, P.M., Chernykh, I.D., On the two-machine routing open shop on a tree with preemption allowed. {\textcopyright} 2022 Agzyamova P.M., Chernykh I.D. This research was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project FWNF-2022-0019), and supported by the Russian Foundation for Basic Research, projects 20-01-00045 and 20-07-00458. Received April, 21, 2022, published August, 26, 2022. Publisher Copyright: {\textcopyright} 2022 Agzyamova P.M., Chernykh I.D.",
year = "2022",
doi = "10.33048/semi.2022.19.046",
language = "English",
volume = "19",
pages = "548--561",
journal = "Сибирские электронные математические известия",
issn = "1813-3304",
publisher = "Sobolev Institute of Mathematics",
number = "2",

}

RIS

TY - JOUR

T1 - On the two-machine routing open shop on a tree with preemption allowed

AU - Agzyamova, P. M.

AU - Chernykh, I. D.

N1 - Funding Information: Agzyamova, P.M., Chernykh, I.D., On the two-machine routing open shop on a tree with preemption allowed. © 2022 Agzyamova P.M., Chernykh I.D. This research was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project FWNF-2022-0019), and supported by the Russian Foundation for Basic Research, projects 20-01-00045 and 20-07-00458. Received April, 21, 2022, published August, 26, 2022. Publisher Copyright: © 2022 Agzyamova P.M., Chernykh I.D.

PY - 2022

Y1 - 2022

N2 - The routing open shop problem is a natural generalization of the metric TSP and a classical open shop scheduling problem. Jobs are located at the nodes of a given transportation network, and mobile machines have to perform operations on those jobs while traveling over the edges. Machines are obligated to return to the initial location after completing all operations. The goal is to minimize the makespan. We consider the two-machine routing open shop on a tree with preemption in a general setting, where travel times are machine and direction-dependent. For this problem we describe a wide polynomially solvable special case, for which the optimal makespan is guaranteed to coincide with the standard lower bound.

AB - The routing open shop problem is a natural generalization of the metric TSP and a classical open shop scheduling problem. Jobs are located at the nodes of a given transportation network, and mobile machines have to perform operations on those jobs while traveling over the edges. Machines are obligated to return to the initial location after completing all operations. The goal is to minimize the makespan. We consider the two-machine routing open shop on a tree with preemption in a general setting, where travel times are machine and direction-dependent. For this problem we describe a wide polynomially solvable special case, for which the optimal makespan is guaranteed to coincide with the standard lower bound.

KW - Asymmetric transportation network

KW - Individual travel times

KW - Polynomially solvable cases

KW - Restricted preemption

KW - Routing open shop

KW - Shop scheduling

KW - Standard lower bound

UR - http://www.scopus.com/inward/record.url?scp=85137639850&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/ea5ccfa0-1b0f-338e-80a2-3ffe6f599e39/

U2 - 10.33048/semi.2022.19.046

DO - 10.33048/semi.2022.19.046

M3 - Article

AN - SCOPUS:85137639850

VL - 19

SP - 548

EP - 561

JO - Сибирские электронные математические известия

JF - Сибирские электронные математические известия

SN - 1813-3304

IS - 2

ER -

ID: 37515234