Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing times

Edwin Tai Chiu Cheng; J. J. Yuan; A. F. Yang

doi:10.1016/j.cor.2003.09.001

Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing times

Edwin Tai Chiu Cheng, J. J. Yuan, A. F. Yang

Research output: Journal article publication › Journal article › Academic research › peer-review

25 Citations (Scopus)

Abstract

We consider the single machine parallel-batching scheduling problem with precedence relations, release dates and identical processing times to minimize a regular objective function. When the processing times are unit, we give an O(n2) time optimal algorithm. When there are no precedence relations, we solve this problem by dynamic programming in O(n3) time. When the precedence relations are "layerly complete", we solve this problem by a dynamic programming algorithm that runs in O(n7) time. For the total weighted completion time minimization problem, we give an O(n2) time 32-approximation algorithm. For the makespan minimization problem, we give an O(n2) time optimal algorithm and an expression of the minimum makespan.

Original language	English
Pages (from-to)	849-859
Number of pages	11
Journal	Computers and Operations Research
Volume	32
Issue number	4
DOIs	https://doi.org/10.1016/j.cor.2003.09.001
Publication status	Published - 1 Apr 2005

Keywords

Algorithms
Batch processing
Identical processing times
Precedence constraints
Release dates
Scheduling

ASJC Scopus subject areas

General Computer Science
Modelling and Simulation
Management Science and Operations Research

More information

10.1016/j.cor.2003.09.001

http://hdl.handle.net/10397/654

Cite this

@article{d67049952b49448b9d7244b520eb46f0,

title = "Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing times",

abstract = "We consider the single machine parallel-batching scheduling problem with precedence relations, release dates and identical processing times to minimize a regular objective function. When the processing times are unit, we give an O(n2) time optimal algorithm. When there are no precedence relations, we solve this problem by dynamic programming in O(n3) time. When the precedence relations are {"}layerly complete{"}, we solve this problem by a dynamic programming algorithm that runs in O(n7) time. For the total weighted completion time minimization problem, we give an O(n2) time 32-approximation algorithm. For the makespan minimization problem, we give an O(n2) time optimal algorithm and an expression of the minimum makespan.",

keywords = "Algorithms, Batch processing, Identical processing times, Precedence constraints, Release dates, Scheduling",

author = "Cheng, {Edwin Tai Chiu} and Yuan, {J. J.} and Yang, {A. F.}",

year = "2005",

month = apr,

day = "1",

doi = "10.1016/j.cor.2003.09.001",

language = "English",

volume = "32",

pages = "849--859",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd",

number = "4",

}

TY - JOUR

T1 - Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing times

AU - Cheng, Edwin Tai Chiu

AU - Yuan, J. J.

AU - Yang, A. F.

PY - 2005/4/1

Y1 - 2005/4/1

N2 - We consider the single machine parallel-batching scheduling problem with precedence relations, release dates and identical processing times to minimize a regular objective function. When the processing times are unit, we give an O(n2) time optimal algorithm. When there are no precedence relations, we solve this problem by dynamic programming in O(n3) time. When the precedence relations are "layerly complete", we solve this problem by a dynamic programming algorithm that runs in O(n7) time. For the total weighted completion time minimization problem, we give an O(n2) time 32-approximation algorithm. For the makespan minimization problem, we give an O(n2) time optimal algorithm and an expression of the minimum makespan.

AB - We consider the single machine parallel-batching scheduling problem with precedence relations, release dates and identical processing times to minimize a regular objective function. When the processing times are unit, we give an O(n2) time optimal algorithm. When there are no precedence relations, we solve this problem by dynamic programming in O(n3) time. When the precedence relations are "layerly complete", we solve this problem by a dynamic programming algorithm that runs in O(n7) time. For the total weighted completion time minimization problem, we give an O(n2) time 32-approximation algorithm. For the makespan minimization problem, we give an O(n2) time optimal algorithm and an expression of the minimum makespan.

KW - Algorithms

KW - Batch processing

KW - Identical processing times

KW - Precedence constraints

KW - Release dates

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=5644246437&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2003.09.001

DO - 10.1016/j.cor.2003.09.001

M3 - Journal article

SN - 0305-0548

VL - 32

SP - 849

EP - 859

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 4

ER -

Scheduling a batch-processing machine subject to precedence constraints, release dates and identical processing times

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this