More Web Proxy on the site http://driver.im/

article

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

Authors:

Bertrand M. T. LinAuthors Info & Claims

Computers and Industrial Engineering, Volume 60, Issue 4

Pages 690 - 698

https://doi.org/10.1016/j.cie.2011.01.002

Published: 01 May 2011 Publication History

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(n^2) 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.

References

[1]

Approximation algorithms for UET scheduling problems with exact delays. Operations Research Letters. v35. 533-540.

Digital Library

[2]

Approximation algorithms for scheduling problems with exact delays. Lecture Notes in Computer Sciences. v4368. 1-14.

Digital Library

[3]

An exact algorithm for scheduling identical coupled tasks. Mathematical Methods of Operations Research. v59. 193-203.

[4]

A note on scheduling identical coupled tasks in logarithmic time. Discrete Applied Mathematics. v158. 583-587.

Digital Library

[5]

Improved analysis of an algorithm for the coupled task problem with UET jobs. Operations Research Letters. v37. 93-96.

Digital Library

[6]

Scheduling of coupled tasks with unit processing times. Journal of Scheduling. v13. 453-461.

Digital Library

[7]

Makespan minimization in the two-machine flowshop batch scheduling problem. Naval Research Logistics. v47. 128-144.

[8]

Davis, T. (2006). Catalan number. <http://www.geometer.org/mathcircles>.

[9]

Hwang, F. J., Kovalyov, M. Y., & Lin, B. M. T. (2010). Minimization of total completion time in flowshop scheduling subject to fixed job sequences. In Proceedings of 12th international workshop on project management and scheduling, Tours, France (pp. 249-252).

[10]

Li, H., & Zhao, H. (2007). Scheduling coupled-tasks on a single machine. In Proceedings of 2007 IEEE symposium on computational intelligence in scheduling, Honolulu, Hawaii (pp. 137-142).

[11]

Total completion time minimization in a 2-stage differentiation flowshop with fixed sequences per job type. Information Processing Letters. v111. 208-212.

Digital Library

[12]

Batching and scheduling in a multi-machine flow shop. Journal of Scheduling. v10. 353-364.

Digital Library

[13]

On the complexity of coupled-task scheduling. Discrete Applied Mathematics. v72. 141-154.

Digital Library

[14]

The open shop scheduling problem with a given sequence of jobs on one machine. Naval Research Logistics. v45. 705-731.

[15]

Scheduling coupled tasks. Naval Research Logistics Quarterly. v27. 489-498.

[16]

Interleaving two-phased jobs on a single machine. Discrete Optimization. v2. 348-361.

Digital Library

[17]

Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard. Journal of Scheduling. v7. 333-348.

Digital Library

Cited By

Khatami MSalehipour A(2021)Coupled task scheduling with time-dependent processing timesJournal of Scheduling10.1007/s10951-020-00675-224:2(223-236)Online publication date: 1-Apr-2021
https://dl.acm.org/doi/10.1007/s10951-020-00675-2
Chen BZhang X(2021)Scheduling coupled tasks with exact delays for minimum total job completion timeJournal of Scheduling10.1007/s10951-020-00668-124:2(209-221)Online publication date: 1-Apr-2021
https://dl.acm.org/doi/10.1007/s10951-020-00668-1
Lin BHwang FKononov A(2018)Relocation scheduling subject to fixed processing sequencesJournal of Scheduling10.1007/s10951-015-0455-819:2(153-163)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.1007/s10951-015-0455-8

Coupled-task scheduling on a single machine subject to a fixed-job-sequence
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Two-machine flowshop scheduling with three-operation jobs subject to a fixed job sequence

This paper studies the problem of scheduling three-operation jobs in a two-machine flowshop subject to a predetermined job processing sequence. Each job has two preassigned operations, which are to be performed on their respective dedicated machines, ...
Coupled task scheduling with convex resource consumption functions
Abstract
We study a single machine scheduling problem with coupled tasks under limited resource availability. Each job comprises of two tasks which are separated by an exact amount of delay. We assume that the processing time of the initial ...
Single machine group scheduling under decreasing linear deterioration

This paper considers single machine scheduling problems with group technology (GT) and deteriorating jobs. A sequence independent setup is required to process a job from a different group and jobs in each group are processed together. We consider the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Industrial Engineering

Computers and Industrial Engineering Volume 60, Issue 4

May, 2011

410 pages

ISSN:0360-8352

Issue’s Table of Contents

Copyright © Elsevier Ltd © 2011.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 May 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Khatami MSalehipour A(2021)Coupled task scheduling with time-dependent processing timesJournal of Scheduling10.1007/s10951-020-00675-224:2(223-236)Online publication date: 1-Apr-2021
https://dl.acm.org/doi/10.1007/s10951-020-00675-2
Chen BZhang X(2021)Scheduling coupled tasks with exact delays for minimum total job completion timeJournal of Scheduling10.1007/s10951-020-00668-124:2(209-221)Online publication date: 1-Apr-2021
https://dl.acm.org/doi/10.1007/s10951-020-00668-1
Lin BHwang FKononov A(2018)Relocation scheduling subject to fixed processing sequencesJournal of Scheduling10.1007/s10951-015-0455-819:2(153-163)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.1007/s10951-015-0455-8

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents