Quantity-based buffer-constrained two-machine flowshop problem: active and passive prefetch models for multimedia applications

摘要

Conventional studies on buffer-constrained flow-shop scheduling problems have considered applications with a limitation on the number of jobs that are allowed in the intermediate storage buffer before flowing to the next machine. The study in Lin et al. (Comput. Oper. Res. 36(4): 1158-1175, 2008a) considered a two-machine flow-shop problem with "processing time-dependent" buffer constraints for multimedia applications. A "passive" prefetch model (the PP-problem), in which the download process is suspended unless the buffer is sufficient for keeping an incoming media object, was applied in Lin et al. (Comput. Oper. Res. 36(4):1158-1175, 2008a). This study further considers an "active" prefetch model (the AP-problem) that exploits the unoccupied buffer space by advancing the download of the incoming object by a computed maximal duration that possibly does not cause a buffer overflow. We obtain new complexity results for both problems. This study also proposes a new lower bound which improves the branch and bound algorithm presented in Lin et al. (Comput. Oper. Res. 36(4):1158-1175, 2008a). For the PP-problem, compared to the lower bounds developed in Lin et al. (Comput. Oper. Res. 36(4): 1158-1175, 2008a), on average, the results of the simulation experiments show that the proposed new lower bound cuts about 38% of the nodes and 32% of the execution time for searching the optimal solutions.