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

Jin Young Choi

International Journal of Production Research, 2015, vol. 53, issue 9, 2605-2616

Abstract: 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 s$ s $, explicitly identifying j$ j $-job instances and feasible y$ y $-processing steps for them to be proceeded, (ii) generating a new state s′$ s^{\prime } $ by applying the (j,y)$ (j, y) $-choice to the state s$ s $ and (iii) determining the safety of the state s$ s $ by checking if all the resources required by all the job instances in the state s′$ s^{\prime } $ up to completion are available. The algorithm iteratively applies these steps to a state by changing the values of j$ j $ and y$ y $, 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.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2014.970710 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tprsxx:v:53:y:2015:i:9:p:2605-2616

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2014.970710

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().