Minimizing Total Flow Time in Single Machine Environment with Release Time

Publication Type

Journal Article

Publication Date

11-2004

Abstract

We study the problem of minimizing total flow time on a single machine with job release times. This problem is NP-complete for which is no constant ratio approximation algorithm. Our objective is to study experimentally how well, on average, the problem can be solved. The algorithm we use produces non-preemptive schedules converted from preemptive ones. We evaluate average solution quality for the problem to identify the characteristics of difficult instances. Results obtained are compared with those recently obtained by other researchers. Based on extensive experiments, we also develop an empirical model to predict solution quality using interpolation.

Keywords

Experimental analysis, Flow time, Machine scheduling, Performance prediction

Discipline

Operations and Supply Chain Management

Research Areas

Operations Management

Publication

Computers and Industrial Engineering

Volume

47

Issue

2

First Page

123

Last Page

140

ISSN

0360-8352

Identifier

10.1016/j.cie.2004.06.004

Publisher

Elsevier

Additional URL

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

Link to Full Text

Share

COinS