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 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.
Experimental analysis, Flow time, Machine scheduling, Performance prediction
Operations and Supply Chain Management
Computers and Industrial Engineering
GUO, Yunsong; LIM, Andrew; RODRIGUES, Brian; and YU, Shuang.
Minimizing Total Flow Time in Single Machine Environment with Release Time. (2004). Computers and Industrial Engineering. 47, (2), 123-140. Research Collection Lee Kong Chian School Of Business.
Available at: http://ink.library.smu.edu.sg/lkcsb_research/2565