Scheduling jobs with shared additional operations on parallel identical machines

Zinder, Y; Berlińska, J; Lin, BMT

Scheduling jobs with shared additional operations on parallel identical machines

Zinder, Y

Berlińska, J Lin, BMT

Permalink

Publisher:: PERGAMON-ELSEVIER SCIENCE LTD
Publication Type:: Journal Article
Citation:: Computers and Operations Research, 2024, 170
Issue Date:: 2024-10-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published versionAdobe PDF (702.22 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Zinder, Y https://orcid.org/0000-0003-2024-8129
dc.contributor.author	Berlińska, J
dc.contributor.author	Lin, BMT
dc.date.accessioned	2025-01-16T06:18:36Z
dc.date.available	2025-01-16T06:18:36Z
dc.date.issued	2024-10-01
dc.identifier.citation	Computers and Operations Research, 2024, 170
dc.identifier.issn	0305-0548
dc.identifier.issn	1873-765X
dc.identifier.uri	http://hdl.handle.net/10453/183782
dc.description.abstract	The paper is concerned with assigning jobs, each with associated additional operations, to identical machines. A machine, allocated to a job, must also process all the additional operations associated with this job. An additional operation that is associated with several jobs assigned to the same machine needs to be processed by this machine only once. The goal is to minimise the time needed for the completion of all jobs and their additional operations. It is shown that even very restricted particular cases of the considered problem remain NP-hard in the strong sense. For the general case, the paper introduces two mixed integer linear programs as well as a broad class of approximation algorithms and a performance guarantee that is valid for any algorithm in this class. It is shown that, for one of the above-mentioned NP-hard particular cases, the considered class contains the best possible approximation algorithm. The performance of the mixed integer linear programs and several approximation algorithms is compared by means of computational experiments.
dc.language	English
dc.publisher	PERGAMON-ELSEVIER SCIENCE LTD
dc.relation.ispartof	Computers and Operations Research
dc.relation.isbasedon	10.1016/j.cor.2024.106780
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	0102 Applied Mathematics, 0103 Numerical and Computational Mathematics
dc.subject.classification	Operations Research
dc.subject.classification	3509 Transportation, logistics and supply chains
dc.subject.classification	4901 Applied mathematics
dc.title	Scheduling jobs with shared additional operations on parallel identical machines
dc.type	Journal Article
utslib.citation.volume	170
utslib.for	0102 Applied Mathematics
utslib.for	0103 Numerical and Computational Mathematics
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Science
pubs.organisational-group	University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	open_access	*
dc.rights.license	This work is licensed under a Creative Commons Attribution 4.0 International License (CC BY 4.0). To view a copy of this license, visit https://creativecommons.org/licenses/by/4.0/
dc.date.updated	2025-01-16T06:18:34Z
pubs.publication-status	Published
pubs.volume	170

Abstract:

The paper is concerned with assigning jobs, each with associated additional operations, to identical machines. A machine, allocated to a job, must also process all the additional operations associated with this job. An additional operation that is associated with several jobs assigned to the same machine needs to be processed by this machine only once. The goal is to minimise the time needed for the completion of all jobs and their additional operations. It is shown that even very restricted particular cases of the considered problem remain NP-hard in the strong sense. For the general case, the paper introduces two mixed integer linear programs as well as a broad class of approximation algorithms and a performance guarantee that is valid for any algorithm in this class. It is shown that, for one of the above-mentioned NP-hard particular cases, the considered class contains the best possible approximation algorithm. The performance of the mixed integer linear programs and several approximation algorithms is compared by means of computational experiments.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/183782