Maximizing the Total Weighted Operating Time for Surgery Scheduling via Linear Program Randomized Rounding Algorithms.

Saved in:

Bibliographic Details
Title:	Maximizing the Total Weighted Operating Time for Surgery Scheduling via Linear Program Randomized Rounding Algorithms.
Authors:	CHEN, PO-AN¹ poanchen@nycu.edu.tw, CHENG, YA-WEN¹ cyw7791.iim.mg09@nycu.edu.tw, WU, TSUNG-JUI¹ 111012912jerry@gmail.com, LIU, TZE-WEI¹ mark6184551@gmail.com
Source:	Journal of Information Science & Engineering. May2026, Vol. 42 Issue 3, p559-570. 12p.
Subjects:	Integer programming, Scheduling, Linear programming, Approximation algorithms, Algorithms
Abstract:	A surgery scheduling problem has been characterized by the integer linear program in the previous work. The objective function is to maximize the total weighted operating time of the week, which equivalently minimizes the idle time on the operating rooms (ORs). The constraints ensure that each operation can only be scheduled once and guarantee that the total time spent on all operations for all departments does not exceed the working hour of a day. We propose two randomized linear program rounding algorithms to solve the problem approximately and in this paper finally show their performances in terms of approximation ratios with a bounded probability for infeasibility and with a feasibility guarantee, respectively. We also supplement the analytical result with numerical result from experiments. [ABSTRACT FROM AUTHOR]
	Copyright of Journal of Information Science & Engineering is the property of Institute of Information Science, Academia Sinica and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	A surgery scheduling problem has been characterized by the integer linear program in the previous work. The objective function is to maximize the total weighted operating time of the week, which equivalently minimizes the idle time on the operating rooms (ORs). The constraints ensure that each operation can only be scheduled once and guarantee that the total time spent on all operations for all departments does not exceed the working hour of a day. We propose two randomized linear program rounding algorithms to solve the problem approximately and in this paper finally show their performances in terms of approximation ratios with a bounded probability for infeasibility and with a feasibility guarantee, respectively. We also supplement the analytical result with numerical result from experiments. [ABSTRACT FROM AUTHOR]
ISSN:	10162364
DOI:	10.6688/JISE.202605_42(3).0004