Surgical practice administrators need to determine the sequence of surgeries and reserved operating room (OR) time for each surgery in the surgery scheduling process. Both decisions require coordination among multiple ORs and the recovery resource in the postanesthesia care unit (PACU) in a surgical suite. Although existing studies have addressed OR time reservation, surgery sequencing coordination is an open challenge in the stochastic surgical environment. In this paper, we propose an algorithmic solution to this problem based on stochastic optimization. The proposed methodology involves the development of a surrogate objective function that is highly correlated with the original one. The resulting surrogate model has network-structured subproblems after Lagrangian relaxation and decomposition, which makes it easier to solve than the impractically difficult original problem. We show that our proposed approach finds near-optimal solutions in small instances and outperforms benchmark methods by 13%–51% or equivalently an estimated saving of $760–$7,420 per day in surgical suites with 4–10 ORs. Our results illustrate a mechanism to alleviate congestion in the PACU. We also recommend that practice administrators prioritize sequencing coordination over the optimization of OR time reservation in an effort for performance improvement. Furthermore, we demonstrate how administrators should consider the impact of sequencing decisions when making strategic capacity adjustments for the PACU. Summary of Contribution: Our work provides an algorithmic solution to an open question in the field of healthcare operations management. This solution approach involves formulating a surrogate optimization model and exploiting its decomposability and network-structure. In computational experiments, we quantitatively benchmark its performance and assess its benefits. Our numerical results provide unique managerial insights for healthcare leadership.

The problem of scheduling aircraft landings on one or more runways is an interesting problem that is similar to a machine job scheduling problem with sequence-dependent processing times and with earliness and tardiness penalties. The aim is to optimally land a set of planes on one or several runways in such a way that separation criteria between all pairs of planes (not just successive ones) are satisfied. Each plane has an allowable time window as well as a target time. There are costs associated with landing either earlier or later than this target landing time. In this paper, we present a specialized simplex algorithm which evaluates the landing times very rapidly, based on some partial ordering information. This method is then used in a problem space search heuristic as well as a branch-and-bound method for both single- and multiple-runway problems. The effectiveness of our algorithms is tested using some standard test problems from the literature. © 1999 John Wiley & Sons, Inc. Networks 34: 229–241, 1999

In this paper, we present an approach to weighted tardiness job-shop scheduling problems (JSP) using a graph decomposition technique. Our method decomposes a JSP into a series of sub-problems by solving a variant of the generalized assignment problem which we term "VAP". Given a specified assignment cost, VAP assigns operations to mutually exclusive and exhaustive subsets, identifying a partially specified schedule, Compared to a conventional, completely specified schedule, this partial schedule is more robust to shop disturbances, and therefore more useful for planning and control. We have developed assignment heuristics which iteratively update the problem parameters using lower and upper bounds computed from the corresponding schedule. The heuristics are tested on standard test problems. We show that the proposed approach provides a means for extending traditional scheduling capabilities to a much wider spectrum of shop conditions and production scenarios.

In a recent paper we discussed “problem” and “heuristic” spaces which serve as a basis for local search in job shop scheduling problems. By encoding schedules as heuristic, problem pairs (H,P) search spaces can be defined by perturbing problem data and/or heuristic parameters. In this paper we attempt to determined, through computational testing, how these spaces can be successfully searched. Well known local search strategies are applied in problem and heuristic space and compared to Shifting Bottleneck heuristics, and to probabilistic dispatching methods. An interesting result is the good performance of genetic algorithms in problem space. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

This paper presents a new approach to datapath synthesis based on a problem-space genetic algorithm (PSGA). The proposed technique performs concurrent scheduling and allocation of functional units, registers, and multiplexers with the objective of finding both a schedule and an allocation which minimizes the cost function of the hardware resources and the total time of execution. The problem-space genetic algorithm based datapath synthesis system (PSGA-Synth) combines a standard genetic algorithm with a known heuristic to search the large design space in an intelligent manner. PSGA-Synth handles multicycle functional units, structural pipelining, conditional code and loops, and provides a mechanism to specify lower and upper bounds on the number of control steps. The PSGA-Synth was tested on a set of problems selected from the literature, as well as larger problems created by us, with promising results. PSGA-Synth not only finds the best known results for all the test problems examined in a relatively small amount of CPU time, but also has the ability to efficiently handle large problems.>