Search

This paper considers how to schedule appointments for outpatients, for a clinic that is subject to appointment lead-time targets for both new and returning patients. We develop heuristic rules, which are the exact and relaxed appointment scheduling rules, to schedule each new patient appointment (only) in light of uncertainty about future arrivals. The scheduling rules entail two decisions. First, the rules need to determine whether or not a patient's request can be accepted; then, if the request is not rejected, the rules prescribe how to assign the patient to an available slot. The intent of the scheduling rules is to maximize the utilization of the planned resource (i.e., the physician staff), or equivalently to maximize the number of patients that are admitted, while maintaining the service targets on the median, the 95th percentile, and the maximum appointment lead-times. We test the proposed scheduling rules with numerical experiments using real data from the chosen clinic of Tan Tock Seng hospital in Singapore. The results show the efficiency and the efficacy of the scheduling rules, in terms of the service-target satisfaction and the resource utilization. From the sensitivity analysis, we find that the performance of the proposed scheduling rules is fairly robust to the specification of the established lead-time targets.

Batch processors can concurrently process more than one batch and are regularly used in the semiconductor manufacturing industry, particularly in the wafer fabrication stage. The reentrant nature of the wafer fab and the incompatibility of jobs from different job families, combined with the typically long processing times of the batch processor, make the control of batch processors an interesting problem with important implications. Current literature has predominantly assumed that the batch processor exists in isolation, and treats the job arrival pattern it receives as a problem constraint. We propose to control the job arrival pattern of the batch processors by controlling the processor immediately upstream of the batch processor, such that the performance of the over-all system is improved. DOCTOR OF PHILOSOPHY (IMST)

In this dissertation, we focus on deriving globally optimal algorithms for three specialized fractional programming problems arising in the context of the independent set problem and management applications in wireless communications. Most of the research efforts thus far involving fractional programs have focused on solving various classes of the single-ratio fractional programs, or multi-ratio cases involving linear fractional functions. However, fractional programming problems become substantially more difficult as the number of ratios in the objective function increases, and this complexity is further amplified when the involved terms are higher-order polynomials. While some classes of multiple-ratio problems can be solved to optimality by recasting them as equivalent 0-1 mixed-integer programming problems, and embedding them within a tailored branch-and-bound algorithm, there is yet significant scope to devise specialized algorithms for solving the generic class of sum of ratios fractional programs, particularly for the case where the involved functions are higher-degree polynomials. We begin by investigating continuous optimization approaches, notably fractional programming methods, to determine the stability number (or independence number) of a graph. Traditionally, this problem has been solved using integer programming methods, but these methods have been known to suffer from a number of shortcomings, in addition to the complexity of dealing with discrete variables. In this context, a new class of vertex sets is defined, and the structure of these vertex sets is utilized to derive explicit characterizations of the number of alternate optima present in both discrete and continuous formulations. Moreover, these vertex sets also enable a simple, yet powerful, construction procedure to efficiently determine maximal independent sets. We also develop a global optimization algorithm to solve the FP formulation, and we demonstrate that this continuous approach stays on par with the 0-1 discrete formulation with respect to various performance metrics. As seen in our numerical experiments, we showed that the computational time required per optimal solution is comparable and in some instances lower for Problem FP as compared to Problem MIS (as the number of alternate optima for Problem FP is significantly greater when compared to Problem MIS) Having established the importance of fractional programming formulations as a viable source for solving hard optimization problems, in the next phase of this research, we focus on solving real-world applications arising in the context of cellular network design. We present a set of (exact and approximate) mathematical models and algorithms for determining the set of (globally) optimal distributed antenna deployments and the supported user demand in cellular code division multiple access (CDMA) systems. We focus on the uplink (user-to-base) formulation and assume that the base station combines all the received signals at each of the antennas using path-gain based weights. In CDMA systems, as all users occupy the system bandwidth at the same time thereby interfering with each other, this results in complicated mixed-integer 0-1 multi-linear programming problem, where the objective function maximizes the total system capacity, while ensuring that the minimum signal-to-interference plus noise ratio (SINR) constraints and maximum transit power constraints for each user are satisfied. This highly nonlinear, nonconvex problem is reformulated to yield a tight mixed-integer 0-1 linear programming representation via the addition of several auxiliary variables and constraints, and a specialized algorithm is designed to determine globally optimal solutions. Finally, we extend the above developed methodology for optimally locating DAS antennas in CDMA cellular networks in the presence of femtocells. Although a femtocell is a simple plug-and-play device, its location requires pre-approval by the service provider. The introduction of femtocells into a cellular network can be very beneficial to both service providers as well as end users. Once again, our focus is on developing an analytical framework that provides a way of computing optimal DAS deployments so that the total capacity is maximized in the CDMA cellular network. Such a framework would be critical for service providers who are interested in adopting the use of femtocells. In conclusion, this thesis provides an algorithmic framework for deriving globally optimal solutions for the class of fractional programming problems, and this approach is validated by solving various practical problems arising in engineering and management applications. Doctor of Philosophy (MAE)