Minimizing Total Flow Time in Single Machine Environment with Release Time

Minimizing Total Flow Time in Single Machine Environment with Release Time

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 n...

Full description

Saved in:
Bibliographic Details
Main Authors: GUO, Yunsong, LIM, Andrew, RODRIGUES, Brian, YU, Shuang
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2004
Subjects:
Experimental analysis
Flow time
Machine scheduling
Performance prediction
Operations and Supply Chain Management
Online Access:https://ink.library.smu.edu.sg/lkcsb_research/2565
https://doi.org/10.1016/j.cie.2004.06.004
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
Description
Summary: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.

Similar Items