Robust single machine scheduling for minimizing total flow time in the presence of uncertain processing times |
| |
| Affiliation: | 1. Institute of Information Management, National Taipei University of Technology, Taipei, Taiwan;2. Department of Industrial Engineering and Management, National Taipei University of Technology, Taipei, Taiwan;3. Department of Information Management, Chang Gung University, Taoyuan, Taiwan;1. Department of Industrial Engineering, Wuhan University of Science and Technology, Wuhan, Hubei, China;2. Department of Chemical and Biological Engineering, Princeton University, Princeton, NJ 08540, USA;3. State Key Laboratory of Multiphase Complex Systems, Institute of Process Engineering, Beijing 100190, China |
| |
| Abstract: | This research deals with the single machine scheduling problem (SMSP) with uncertain job processing times. The single machine robust scheduling problem (SMRSP) aims to obtain robust job sequences with minimum worst-case total flow time. We describe uncertain processing times using intervals, and adopt an uncertainty set that incorporates a budget parameter to control the degree of conservatism. A revision of the uncertainty set is also proposed to address correlated uncertain processing times due to a number of common sources of uncertainty. A mixed integer linear program is developed for the SMRSP, where a linear program for determining the worst-case total flow time is integrated within the conventional integer program of the SMSP. To efficiently solve the SMRSP, a simple iterative improvement (SII) heuristic and a simulated annealing (SA) heuristic are developed. Experimental results demonstrate that the proposed SII and SA heuristics are effective and efficient in solving SMRSP with practical problem sizes. |
| |
| Keywords: | Robust scheduling Single machine Total flow time |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
