Overview of Cyclic Bottleneck Problem

Abstract

In this paper, we are going to overview a new variant of the classical assignment problem referred to as the cyclic bottleneck assignment problem (CBAP). This problem can arise in the healthcare industry or supply chain management. The problem can arise in surgical room scheduling and can be described as follows. Each of m successive time units can be allocated to any of the m surgeons available. The number of patients to be scheduled for surgery on a given unit and the length of stay of the patient in the recovery unit are dependent on the type of surgery. The problem is to assign one surgeon to each OR time so as to minimize the maximum number of patients that will be expected to occupy the recovery unit in the long run. In this paper we have compared various ways through which the CBAP has been solved , that is Cohort Intelligence[4] , Tabu Search[2] and Iterated Local Search.

Introduction

I. INTRODUCTION

An assignment problem is a particular case of transportation problem. The objective is to assign a number of resources to an equal number of activities. So as to minimize total cost or maximize total profit of allocation. The problem of assignment arises because available resources such as men, machines etc. have varying degrees of efficiency for performing different activities, therefore, cost, profit or loss of performing the different activities is different. Cyclic Bottleneck Assignment Problem is the new variant of cyclic assignment problem. CBAP is a NP hard algorithm. Consider a hospital that wants to schedule n surgeons to perform surgical operations over a time horizon. For planning purposes, the hospital divides the time horizon into n discrete time slots (e.g. days). The schedule necessitates that one surgeon be assigned to one and only one time slot over the planning horizon. Furthermore, the number of patients to be operated on in a given time slot and the length of stay of each operated patient in the recovery unit depends on the type of surgery performed. The objective function is to minimize the maximum beds or resources used and to ensure that each surgeon is assigned to exactly one time slot and vice versa. The term bottleneck refers to the min-max objective function. The purpose of this paper is to compare the methods which are used for finding the optimal solutions for CBAP which is cohort intelligence, tabu search and iterative local search.

II. LITERATURE SURVEY

The classical assignment problem (CAP) is stated as finding a minimum-cost assignment of tasks to agents such that each task is assigned to exactly one agent and such that each agent's resource capacity is honored. Researchers have proposed a number of variations of the classic assignment problem and developed various algorithms to solve them.The variations are mostly different in the way the objective functions are modeled.The variation of the assignment problem shares features with three important variants of the problem namely the bottleneck assignment problem, quadratic assignment problem and cyclic bottleneck assignment problem.

The Bottleneck assignment problem is defined based on a set of agents that must be assigned to a set of tasks while ensuring that each task is done by one agent.

In other words, we want an assignment that will minimize the maximum individual cost.The usage of the word “bottleneck”, meaning the neck or mouth of a bottle, comes from a popular application of this problem in timed tasks performed by a specific person. In this context, we seek the minimization of the maximum duration, i.e. we make the neck of the schedule of the whole job to minimize tightness.

QAP is a combinatorial optimization problem. QAP can be described as assignment problem of n facilities to n locations, which minimizes the sum of the total quadratic interaction cost, the flow between the facilities multiplied with their distances, and the total cost associated with allocating a facility to a certain location.

Cyclic Scheduling means when the schedule is charted over at the end of each planning period. The goal of cbap is to minimize the max no of resources used. Cyclic refers to the row circularity of matrix C; bottleneck refers to the min max objective; and assignment refers to the problem’s close affinity to the classical assignment problem that minimizes the resources.

III. METHODS

A. Cohort Intelligence Algorithm[4]

CI is based on artificial intelligence (AI) concepts which attempts to model the behavior in a self organizing system. In which candidates in a cohort interact and compete with one another in order to accomplish the shared goals. They try to improve their own behavior by observing the behavior of every other candidate in that cohort. Each candidate in the cohort follows a certain behavior which may lead to its own behavioral improvement. In this way, candidates in the cohort learn from one another which, in time, helps improve the behavior of the entire group. The cohort’s behavior as a whole is said to have reached saturation (convergence) if, over a considerable number of learning attempts, the individual behavior of all candidates does not improve considerably making it hard to distinguish amongst themselves. In other words, the difference between the individual behaviors of the candidates becomes insignificant.

B. Tabu Search[2]

Tabu search used for mathematical optimization is a metaheuristic local search method. Local search methods have high possibilities to be stuck in suboptimal regions. TS improves the performance of these techniques by prohibiting already visited solutions or others through user-provided rules. Previously TS is applied to solving MINLPs with master-slave structure. The master loop deals with all the integer variables using TS, and the inner loop minimizes each NLP subp. NLP subproblems are then solved for each candidate using the gradient-based method. Among all the new candidates, the one with the best objective value is considered and treated as a seed to generate the next generation of candidates. A tabu list is built to forbid the selection of already visited solutions and their neighborhoods, to prevent being trapped into local optima.

C. Iterated Local Search

The ILS is based on a local search strategy using a single solution along the iterative process. ILS is a low–computational time method, which is useful in high-dimensional problems, used to improve the quality of local optima. Generally, the process performed by the ILS method starts with a random initial solution (binary encoding) within the predefined search space, and the stopping criterion can be a number of iterations. The steps of local search, perturbation, and the stopping criterion are the fundamental idea of the ILS .

IV. DISCUSSIONS

A. Cohort Intelligence Algorithm For Solving CBAP[4]

In the CI algorithm the elements of rearrangement vectors are considered the attributes/characteristics that candidates in cohort select and are associated with. The procedure begins with the initialisation of number of cohort candidates S, number of variations Y, the permutation pi of every candidate s,the convergence parameter E and the maximum number of allowable learning attempts L(max).

In a cohort of S candidates every element randomly generates a permutation. Every candidate S forms a matrix by applying its permutation and rotating all corresponding n rows of matrix accordingly. This way S matrices are formed. . Next the associated vector of maximum column sums is calculated. As a minimisation problem the probability of selecting a column sum of every candidate is calculated. Every candidate using a roulette wheel approach then selects a candidate S in cohort to follow ie it incorporates an element within its existing permutation and then every candidate generates permutations say Y. the minimum of every candidate is then found. If the maximum number of learning attempts is exceeded or The cohort reaches a saturation state then we can accept any of the matrices from within the pool of current available

rotated matrices as the final solution , if not proceed with process again

B. Tabu Search Algorithm For Solving CBAP

In the tabu search method, the algorithm starts by exploring the neighborhood of the current solution and usually makes use of an improvement strategy to select the best neighbor at every iteration. To prevent our local search algorithm from returning back to a previously visited candidate immediately which may lead to cycling , tabu search uses the tabu lists.

In tabu Search for CBAP , the search memory is utilized to help generation of neighboring solutions. In simpler words , when our current solution, suppose X , does not belong to our memory list M , three operators - exchange , relocate and reverse are implemented to generate the next neighboring solution. But if the solution has previously occurred in our memory list, then 3-OPT and 4-OPT operators are invoked to perturb the solution so that the diversification can be increased.

C. Iterated Local Search Algorithm For Solving CBAP

The underlying idea of the ILS is to perform a biased, randomized walk in the space of locally optimal solutions, instead of sampling the space of all possible candidate solutions. This walk is built in by iteratively applying first a per- turbation to a locally optimal solution, then applying a local search approach, and finally using an acceptance criterion which determines to which locally optimal solution the next perturbation is applied.

Tabu Search[2] is used to generate an initial solution for subsequent iterations. The local search is implemented by applying to the current solution X ,five neigh- boring operators which are introduced in Tabu Search. ILS-CBAP escapes from local optima by applying perturbations to the current local minimum. The procedure Acceptance Criterion determines whether the solution X’ returned by the local search, is accepted or not as the new current solution fDor subsequent iterations.

It can be used to control the balance between intensi?cation and diversi?cation of that search .Basically X' is always accepted if it is better than X. Otherwise, if X' is worse than X, solution X' is accepted with probability exp(f(χ)− f(χ”))/T0, where T0 is a parameter called temperature.

V. FUTURE SCOPE

The CBAP method is widely used in the healthcare and inventory management industry. In future the method can be solved using various other algorithms like ant colony and particle optimisation methods and the results can be compared to get an optimum solution.

• Acknowledgement: We thank Dr Anand Kulkarni, Dept of AI,MITWPU for his efforts and help

Conclusion

In this paper, we have studied the cyclic bottleneck assignment problem, which arises in various contexts including healthcare and inventory management, and has been proven to be NP- hard. To solve this method , we have studied and understood three approaches namely Cohort Intelligence[4] , Tabu Search and Iterated Local Search method. The cohort intelligence algorithm is successfully applied to solve the cyclic bottleneck assignment problem leading to the conclusion that candidates in cohort learn from one another which helps improve the behavior of the entire group. For benchmark and newly generated instances both Tabu and Iterated Search have similar performance, whereas for randomly generated ILS outperforms Tabu Search slightly.

References

[1] Yi, N., Xu, J., Yan, L. and Huang, L., 2020. Task optimization and scheduling of distributed cyber–physical system based on improved ant colony algorithm. Future Generation Computer Systems, 109, pp.134-148. [2] Li, X., Zhu, L., Baki, F. and Chaouch, A.B., 2018. Tabu search and iterated local search for the cyclic bottleneck assignment problem. Computers & Operations Research, 96, pp.120-130. [3] Dorigo, M., Birattari, M. and Stutzle, T., 2006. Ant colony optimization. IEEE computational intelligence magazine, 1(4), pp.28-39. [4] Kulkarni, A.J., Durugkar, I.P. and Kumar, M., 2013, October. Cohort intelligence: a self supervised learning behavior. In 2013 IEEE international conference on systems, man, and cybernetics (pp. 1396-1400). IEEE. [5] Patankar, N.S. and Kulkarni, A.J., 2018. Variations of cohort intelligence. Soft Computing, 22(6), pp.1731-1747. [6] Bansal, J.C., 2019. Particle swarm optimization. In Evolutionary and swarm intelligence algorithms (pp. 11-23). Springer, Cham. [7] Chopard, B. and Tomassini, M., 2018. Particle swarm optimization. In An Introduction to Metaheuristics for Optimization (pp. 97-102). Springer, Cham [8] Parsopoulos, K.E. and Vrahatis, M.N., 2019, April. UPSO: A unified particle swarm optimization scheme. In International Conference of Computational Methods in Sciences and Engineering 2004 (ICCMSE 2004) (pp. 868-873). CRC Press. [9] Shastri, A.S. and Kulkarni, A.J., 2018. Multi-cohort intelligence algorithm: an intra-and inter-group learning behaviour based socio-inspired optimisation methodology. International Journal of Parallel, Emergent and Distributed Systems, 33(6), pp.675-715.

Copyright

Copyright © 2023 Stuti Jajodia, Ananya Nigotia, Gargie Nimbalkar, Aditi Baheti, Prof. Madhura Phatak, Dr. Bhavana Tiple. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.