engleski

A VNS-Lagrangean heuristics for scheduling of patients in hospitals

We address the real world problem of how to schedule the treatments of the resident patients in hospitals. The problem considers the patients who have to be subjected to a certain kind of treatment on a given day. There are several kinds of treatments being performed. Each kind of treatment consists of different number of procedures which have to be done in a strictly prescribed sequence. Each procedure is performed on a certain medical machine. Each machine is capacitated in terms of number of patients it can treat in one time unit. Furthermore, treatments of specific patients have different levels of priority, depending on the condition of the patient. On the other hand, we have labor constraints in terms of doctors who are to perform the treatments. However, this is not the case of the classical assignment of labor to the machines because the set of doctors performing the treatments can not be partitioned into disjoint sets according to the type of the machines. Namely, exactly one doctor has to be assigned to each medical machine on which there is a treatment being performed in that moment. Moreover, each doctor is skilled to perform treatments on several kinds of machines, but the fields of their expertise are not disjoint. Furthermore, in one time unit one doctor can work on at most one machine. We model the problem as 0 - 1 integer programming problem. Taking into account the large number of patients and the large number of different kinds of treatments, as well as the fact that we are dealing with the NP-hard problem, we propose a heuristics based on VNS and Lagrangean relaxation.

0-1 integer programming problem; scheduling; labor constraints; resource constraints; job shop; vns; cplex

nije evidentirano