A branch and price algorithm for the pharmacy duty scheduling problem

Date

2016-08-01

Author

Ceyhan, Gokhan
ÖZPEYNİRCİ, NAİL ÖZGÜR

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

76
views

0
downloads

Pharmacy Duty Scheduling (PDS) is the activity of assigning pharmacies to days during a planning horizon with the purpose of serving society outside regular working hours. In Turkey, pharmacies are retailers who operate during the working hours in weekdays. However, demand for medicine at nights, at the weekends and on holidays must be satisfied by allocating times to pharmacies to open at these times. The problem is a multi-period p-median problem with the additional problem specific constraints, and it is NP-Hard. In this study, we develop a branch-and-price algorithm to solve the PDS to optimality. We decompose the problem into single period problems and apply column generation on the decomposed problem. We propose several enhancements on the algorithm and conduct computational tests on randomly generated instances to compare the performance of the developed algorithm with the state-of art general purpose solver. The branch-and-price algorithm outperforms the state-of-art general purpose solver.

Subject Keywords

Management Science and Operations Research, Modelling and Simulation, General Computer Science

URI

https://hdl.handle.net/11511/65348

Journal

COMPUTERS & OPERATIONS RESEARCH

DOI

https://doi.org/10.1016/j.cor.2016.02.007

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

An anticipative scheduling approach with controllable processing times Gürel, Sinan; Akturk, M. Selim (Elsevier BV, 2010-06-01) In practice, machine schedules are usually subject to disruptions which have to be repaired by reactive scheduling decisions. The most popular predictive approach in project management and machine scheduling literature is to leave idle times (time buffers) in schedules in coping with disruptions, i.e. the resources will be under-utilized. Therefore, preparing initial schedules by considering possible disruption times along with rescheduling objectives is critical for the performance of rescheduling decision...
AN INTERACTIVE APPROACH FOR A DUAL CONSTRAINT JOB SHOP SCHEDULING PROBLEM KONDAKCI, S; GUPTA, RM (Elsevier BV, 1991-01-01) Until recently, heuristic dispatching rules were the only practical means to solve the job shop scheduling problem. Currently, a promising direction in job shop scheduling is interactive scheduling. In this study an interactive scheduling approach is developed for a dual-constraint dynamic job shop production environment. The approach is used by a number of subjects in an experiment. The performance of the subjects is compared with that of dispatching rules based on tardiness and other measures relevant...
A conic quadratic formulation for a class of convex congestion functions in network flow problems Gürel, Sinan (Elsevier BV, 2011-06-01) In this paper we consider a multicommodity network flow problem with flow routing and discrete capacity expansion decisions. The problem involves trading off congestion and capacity assignment (or expansion) costs. In particular, we consider congestion costs involving convex, increasing power functions of flows on the arcs. We first observe that under certain conditions the congestion cost can be formulated as a convex function of the capacity level and the flow. Then, we show that the problem can be effici...
Heuristic approaches for solid transportation-p-facility location problem Das, Soumen Kumar; Roy, Sankar Kumar; Weber, Gerhard Wilhelm (Springer Science and Business Media LLC, 2020-09-01) Determining optimum places for the facilities and optimum transportation from existing sites to the facilities belongs to the main problems in supply chain management. Thesolid transportation-p-facility location problem(ST-p-FLP) is an integration between thefacility location problemand thesolid transportation problem(STP). This paper delineates the ST-p-FLP, a generalization of the classical STP in which location ofp-potential facility sites are sought so that the total transportation cost by means of conv...
Scheduling parallel CNC machines with time/cost trade-off considerations Gürel, Sinan (Elsevier BV, 2007-09-01) When the processing times of jobs are controllable, selected processing times affect both the manufacturing cost and the scheduling performance. A well-known example for such a case that this paper specifically deals with is the turning operation on a CNC machine. Manufacturing cost of a turning operation is a nonlinear convex function of its processing time. We also know that scheduling decisions are quite sensitive to the processing times. Therefore, this paper considers minimizing total manufacturing cos...

Citation Formats

G. Ceyhan and N. Ö. ÖZPEYNİRCİ, “A branch and price algorithm for the pharmacy duty scheduling problem,” COMPUTERS & OPERATIONS RESEARCH, pp. 175–182, 2016, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/65348.