A modified bottleneck-based (MB) heuristic for large-scale job-shop scheduling problems with a well- defined bottleneck is suggested,which is simpler but more tailored than the shifting bottleneck (SB) procedure. In t...A modified bottleneck-based (MB) heuristic for large-scale job-shop scheduling problems with a well- defined bottleneck is suggested,which is simpler but more tailored than the shifting bottleneck (SB) procedure. In this algorithm,the bottleneck is first scheduled optimally while the non-bottleneck machines are subordinated around the solutions of the bottleneck schedule by some effective dispatching rules.Computational results indicate that the MB heuristic can achieve a better tradeoff between solution quality and computational time compared to SB procedure for medium-size problems.Furthermore,it can obtain a good solution in a short time for large-scale job- shop scheduling problems.展开更多
The bottleneck analysis of the minimum coat problem for the generalized netwok(MCPGN) is discussed.The analysis is based on the network simplex algorithm,which gains negative cost graphs by constructing augmented fore...The bottleneck analysis of the minimum coat problem for the generalized netwok(MCPGN) is discussed.The analysis is based on the network simplex algorithm,which gains negative cost graphs by constructing augmented forest structure,then augments flows on the negative cost graphs until the optimal revolution is gained Bottleneck structure is presented after analyzing the augmented forest structure.The negative cost augmented graphs are constructed with the bottleneck structure.The arcs that block the negative cost augmented graph are the elements of the bottleneck.The bottleneck analysis for the generalized circulation problem,the minimum circulation problem and the circulation problem are discussed respectively as the basal problems,then that for MCPGN is achieved.An example is presented at the end.展开更多
基金the National Natural Science Foundation of China (6027401360474002)Shanghai Development Found for Science and Technology (04DZ11008).
文摘A modified bottleneck-based (MB) heuristic for large-scale job-shop scheduling problems with a well- defined bottleneck is suggested,which is simpler but more tailored than the shifting bottleneck (SB) procedure. In this algorithm,the bottleneck is first scheduled optimally while the non-bottleneck machines are subordinated around the solutions of the bottleneck schedule by some effective dispatching rules.Computational results indicate that the MB heuristic can achieve a better tradeoff between solution quality and computational time compared to SB procedure for medium-size problems.Furthermore,it can obtain a good solution in a short time for large-scale job- shop scheduling problems.
基金This project is supported by National Natural Science Foundation of China (No.60274013, No.60474002)Shanghai City Development Found for Science and Technology, China(No.04DZ11008)
基金Supported by the National Natural Science Foundation of China (No. 60174046).
文摘The bottleneck analysis of the minimum coat problem for the generalized netwok(MCPGN) is discussed.The analysis is based on the network simplex algorithm,which gains negative cost graphs by constructing augmented forest structure,then augments flows on the negative cost graphs until the optimal revolution is gained Bottleneck structure is presented after analyzing the augmented forest structure.The negative cost augmented graphs are constructed with the bottleneck structure.The arcs that block the negative cost augmented graph are the elements of the bottleneck.The bottleneck analysis for the generalized circulation problem,the minimum circulation problem and the circulation problem are discussed respectively as the basal problems,then that for MCPGN is achieved.An example is presented at the end.
