Maximising the Total Weight of On-Time Jobs on Parallel Machines Subject to a Conflict Graph

Zinder, Y; Berlińska, J; Peter, C

Maximising the Total Weight of On-Time Jobs on Parallel Machines Subject to a Conflict Graph

Zinder, Y

Berlińska, J Peter, C

Permalink

Publisher:: Springer
Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2021, 12755 LNCS, pp. 280-295
Issue Date:: 2021-01-01

Closed Access

	Filename	Description	Size
	Zinder2021_Chapter_MaximisingTheTotalWeightOfOn-T.pdf	Published version	429.34 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

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	Peter, C
dc.date	2021-07-05
dc.date.accessioned	2022-02-10T19:22:23Z
dc.date.available	2022-02-10T19:22:23Z
dc.date.issued	2021-01-01
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2021, 12755 LNCS, pp. 280-295
dc.identifier.isbn	9783030778750
dc.identifier.issn	0302-9743
dc.identifier.issn	1611-3349
dc.identifier.uri	http://hdl.handle.net/10453/154386
dc.description.abstract	The paper considers scheduling on parallel machines under the constraint that some pairs of jobs cannot be processed concurrently. Each job has an associated weight, and all jobs have the same deadline. The objective is to maximise the total weight of on-time jobs. The problem is known to be strongly NP-hard in general. A polynomial-time algorithm for scheduling unit execution time jobs on two machines is proposed. The performance of a broad family of approximation algorithms for scheduling unit execution time jobs on more than two machines is analysed. For the case of arbitrary job processing times, two integer linear programming formulations are proposed and compared with two formulations known from the earlier literature. An iterated variable neighborhood search algorithm is also proposed and evaluated by means of computational experiments.
dc.language	en
dc.publisher	Springer
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.relation.ispartof	International Conference on Mathematical Optimization Theory and Operations Research
dc.relation.isbasedon	10.1007/978-3-030-77876-7_19
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject.classification	Artificial Intelligence & Image Processing
dc.title	Maximising the Total Weight of On-Time Jobs on Parallel Machines Subject to a Conflict Graph
dc.type	Conference Proceeding
utslib.citation.volume	12755 LNCS
utslib.location.activity	Irkutsk, Russia
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	closed_access	*
pubs.consider-herdc	false
dc.date.updated	2022-02-10T19:22:22Z
pubs.finish-date	2021-07-10
pubs.place-of-publication	Switzerland
pubs.publication-status	Published
pubs.start-date	2021-07-05
pubs.volume	12755 LNCS
dc.location	Switzerland

Abstract:

The paper considers scheduling on parallel machines under the constraint that some pairs of jobs cannot be processed concurrently. Each job has an associated weight, and all jobs have the same deadline. The objective is to maximise the total weight of on-time jobs. The problem is known to be strongly NP-hard in general. A polynomial-time algorithm for scheduling unit execution time jobs on two machines is proposed. The performance of a broad family of approximation algorithms for scheduling unit execution time jobs on more than two machines is analysed. For the case of arbitrary job processing times, two integer linear programming formulations are proposed and compared with two formulations known from the earlier literature. An iterated variable neighborhood search algorithm is also proposed and evaluated by means of computational experiments.

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

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