Coupled-task scheduling on a single machine subject to a fixed-job-sequence

Hwang, FJ; Lin, BMT

Coupled-task scheduling on a single machine subject to a fixed-job-sequence

Hwang, FJ

Lin, BMT

Permalink

Publication Type:: Journal Article
Citation:: Computers and Industrial Engineering, 2011, 60 (4), pp. 690 - 698
Issue Date:: 2011-05-01

Closed Access

	Filename	Description	Size
	2012001329OK.pdf	Published Version	922.91 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	Hwang, FJ https://orcid.org/0000-0002-1741-5590	en_US
dc.contributor.author	Lin, BMT https://orcid.org/0000-0003-0456-296X	en_US
dc.date.issued	2011-05-01	en_US
dc.identifier.citation	Computers and Industrial Engineering, 2011, 60 (4), pp. 690 - 698	en_US
dc.identifier.issn	0360-8352	en_US
dc.identifier.uri	http://hdl.handle.net/10453/32451
dc.description.abstract	This paper investigates single-machine coupled-task scheduling where each job has two tasks separated by an exact delay. The objective of this study is to schedule the tasks to minimize the makespan subject to a given job sequence. We introduce several intriguing properties of the fixed-job-sequence problem under study. While the complexity status of the studied problem remains open, an O(n2) algorithm is proposed to construct a feasible schedule attaining the minimum makespan for a given permutation of 2n tasks abiding by the fixed-job-sequence constraint. We investigate several polynomially solvable cases of the fixed-job-sequence problem and present a complexity graph of the problem. © 2010 Published by Elsevier Ltd. All rights reserved.	en_US
dc.relation.ispartof	Computers and Industrial Engineering	en_US
dc.relation.isbasedon	10.1016/j.cie.2011.01.002	en_US
dc.subject.classification	Industrial Engineering & Automation	en_US
dc.title	Coupled-task scheduling on a single machine subject to a fixed-job-sequence	en_US
dc.type	Journal Article
utslib.citation.volume	4	en_US
utslib.citation.volume	60	en_US
utslib.for	0102 Applied Mathematics	en_US
utslib.for	01 Mathematical Sciences	en_US
utslib.for	08 Information and Computing Sciences	en_US
utslib.for	09 Engineering	en_US
pubs.embargo.period	Not known	en_US
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
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical Sciences
utslib.copyright.status	closed_access
pubs.issue	4	en_US
pubs.publication-status	Published	en_US
pubs.volume	60	en_US

Abstract:

This paper investigates single-machine coupled-task scheduling where each job has two tasks separated by an exact delay. The objective of this study is to schedule the tasks to minimize the makespan subject to a given job sequence. We introduce several intriguing properties of the fixed-job-sequence problem under study. While the complexity status of the studied problem remains open, an O(n2) algorithm is proposed to construct a feasible schedule attaining the minimum makespan for a given permutation of 2n tasks abiding by the fixed-job-sequence constraint. We investigate several polynomially solvable cases of the fixed-job-sequence problem and present a complexity graph of the problem. © 2010 Published by Elsevier Ltd. All rights reserved.

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

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