A binary search algorithm for the general coupled task scheduling problem

Khatami, M; Salehipour, A

A binary search algorithm for the general coupled task scheduling problem

Khatami, M

Salehipour, A

Permalink

Publisher:: Springer Science and Business Media LLC
Publication Type:: Journal Article
Citation:: 4OR, 2020, pp. 1-19
Issue Date:: 2020-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted versionAdobe PDF (393.73 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Khatami, M https://orcid.org/0000-0001-6159-9772
dc.contributor.author	Salehipour, A
dc.date.accessioned	2020-12-04T22:49:07Z
dc.date.available	2020-12-04T22:49:07Z
dc.date.issued	2020-01-01
dc.identifier.citation	4OR, 2020, pp. 1-19
dc.identifier.issn	1619-4500
dc.identifier.issn	1614-2411
dc.identifier.uri	http://hdl.handle.net/10453/144501
dc.description.abstract	© 2020, Springer-Verlag GmbH Germany, part of Springer Nature. The coupled task scheduling problem aims to schedule a set of jobs, each with at least two tasks and there is an exact delay period between two consecutive tasks, on a set of machines to optimize a performance criterion. We study the problem of scheduling a set of coupled jobs to be processed on a single machine with the objective of minimizing the makespan, which is known to be strongly NP-hard. We obtain competitive lower bounds for the problem through different procedures, including solving 0-1 knapsack problems. We obtain an upper bound by applying a heuristic algorithm. We then propose a binary search heuristic algorithm for the coupled task scheduling problem. We perform extensive computational experiments and show that the proposed method is able to obtain quality solutions. The results also indicate that the proposed solution method outperforms the standard exact solver Gurobi.
dc.language	en
dc.publisher	Springer Science and Business Media LLC
dc.relation	http://purl.org/au-research/grants/arc/DE170100234
dc.relation.ispartof	4OR
dc.relation.isbasedon	10.1007/s10288-020-00463-w
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	This is a post-peer-review, pre-copyedit version of an article published in 4OR. The final authenticated version is available online at: https://dx.doi.org/10.1007/s10288-020-00463-w.	en_US
dc.subject	0102 Applied Mathematics, 1503 Business and Management
dc.subject.classification	Operations Research
dc.title	A binary search algorithm for the general coupled task scheduling problem
dc.type	Journal Article
utslib.for	0102 Applied Mathematics
utslib.for	1503 Business and Management
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney
utslib.copyright.status	open_access	*
dc.date.updated	2020-12-04T22:48:57Z
pubs.publication-status	Published

Abstract:

© 2020, Springer-Verlag GmbH Germany, part of Springer Nature. The coupled task scheduling problem aims to schedule a set of jobs, each with at least two tasks and there is an exact delay period between two consecutive tasks, on a set of machines to optimize a performance criterion. We study the problem of scheduling a set of coupled jobs to be processed on a single machine with the objective of minimizing the makespan, which is known to be strongly NP-hard. We obtain competitive lower bounds for the problem through different procedures, including solving 0-1 knapsack problems. We obtain an upper bound by applying a heuristic algorithm. We then propose a binary search heuristic algorithm for the coupled task scheduling problem. We perform extensive computational experiments and show that the proposed method is able to obtain quality solutions. The results also indicate that the proposed solution method outperforms the standard exact solver Gurobi.

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

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