Design and comparative performance analysis of a heuristic-based parameterised Banker's algorithm using the CRL scheduling problems

作者：Choi Jin Young^*

来源：International Journal of Production Research, 2015, 53(9): 2605-2616.

DOI：10.1080/00207543.2014.970710

• effectiveness
• comparative performance analysis
• Heuristic-based parameterised Banker's algorithm
• capacitated re-entrant line
• polynomial-kernel deadlock avoidance policy
• operational flexibility

In this paper, we suggest an efficient sub-optimal deadlock avoidance policy (DAP), called a heuristic-based parameterised Banker's algorithm (H-pBA). It has the main three steps such as (i) for a state
[GRAPHICS]
, explicitly identifying
[GRAPHICS]
-job instances and feasible
[GRAPHICS]
-processing steps for them to be proceeded, (ii) generating a new state
[GRAPHICS]
by applying the
[GRAPHICS]
-choice to the state
[GRAPHICS]
and (iii) determining the safety of the state
[GRAPHICS]
by checking if all the resources required by all the job instances in the state
[GRAPHICS]
up to completion are available. The algorithm iteratively applies these steps to a state by changing the values of
[GRAPHICS]
and
[GRAPHICS]
, up to their upper bounds in the worst case, until it makes a decision about the safety. For performance evaluation, we perform a comparative performance analysis by conducting numerical experiments using a set of prototypical examples for capacitated re-entrant line (CRL) configurations, while comparing with the most common polynomial-kernel DAPs reported in the literature. By suggesting two performance indices representing the operational flexibility and effectiveness, we show that the performance of the suggested H-pBA is consistently superior to that of other PK-DAPs, and furthermore, it is beneficial to integrate it with the first-buffer first-serve policy for system throughput in the CRL.

• 出版日期2015-5-3