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.

This paper introduces a deterministic model to plan the physician requirements for outpatient clinics to achieve service targets for the appointment lead-times of patients. The Ministry of Health of Singapore has established targets for the median, 95th percentile, and 100th percentile of appointment lead-times for patients, since long appointment postponements are regarded as being unacceptable for health care services. The study is to match the capacity of the healthcare providers to the patient demand for a re-entry system, subject to restrictions on the appointment lead-times for patients. We propose a mixed-integer programming model for planning capacity with the minimization of the maximum required capacity as its objective. In the model we assume a finite planning horizon, deterministic arrivals, multiple types of patients, identical physicians, and dependent demand between types of patients. We solve this model with a Branch and Cut algorithm. We test the model with numerical experiments using real data from the chosen specialty at the outpatient clinic of the studied hospital. The results show the value of the proposed model via a systematic push-pull mechanism in scheduling patients' requests to minimize the objective. The clinic should use one of the appointment lead-time targets to determine the patients' appointment dates. Finally, from the sensitivity analyses we demonstrate that the objective is negatively correlated with first-visit patients' appointment lead-time targets, the discharge rates, and the re-visit patients' mean appointment lead-time; we find a positive correlation between the first-visit patients' mean appointment lead-time and the appointment lead-time targets.

This paper deals with a flow-shop scheduling problem with limited intermediate buffer. Jobs are grouped in incompatible job families. Each job has to be processed by a batch processor followed by a discrete processor in the same order. The batch processor can process several jobs simultaneously so that all jobs of the same batch start and complete together. We assume that the capacity of batch processor is bounded. The batch processing time is identical for batches of the same family. A batch which has completed processing on the batch processor may block the processor until there is a free unit in the buffer. The objective is to determine a batching and scheduling for all jobs so as to minimise mean completion time. A lower bound and two heuristics algorithm are developed. Moreover, a two-stage method embedded with a Differential Evolution (DE) algorithm is also developed. DE is one of the latest evolutionary computation algorithms, which implements mutation, crossover, and selection operators to improve the candidate solutions iteratively. Three variants of DE are first compared with a continuous Genetic Algorithm employing the random key representation. Then, one variant of the DE with the best convergence speed is selected. Numerical experiments are conducted to evaluate the performances of the selected two-stage meta-heuristic and two heuristics.

We analyse the problem of minimising the mean cycle time of a batch processing stage containing K > 1 batch processors in parallel with incompatible job families and future job arrivals. We provide an integer linear programming formulation and a dynamic program formulation for small problem instances. For larger problem instances, we propose an online heuristic policy MPC_REPEAT. At each instance a decision has to be made, MPC_REPEAT decomposes the problem of simultaneously assigning multiple batches to multiple processors into sequentially assigning multiple batches to multiple processors. When job families are uncorrelated, we show via simulation experiments that MPC_REPEAT has significantly lower mean cycle time than a previously proposed look-ahead method except when: (MPC_REPEAT ignores some job families AND the traffic intensity is high.) Our experiments also reveal that increasing the job family correlation of consecutive job arrivals results, with a few exceptions, in a mean cycle-time reduction, for both policies evaluated. This reduction in cycle time generally increases with: increasing number of job families, decreasing number of processors, and increasing time between job arrivals. Our findings imply that controlling the upstream processors, such that job families of consecutive job arrivals are correlated, can reduce the cycle time at the batch processing stage. Furthermore, the expected mean cycle time reduction due to this strategy can be substantially larger than that expected from switching to a more complex batch processing stage policy, under less stringent conditions.

This paper addresses the problem of minimizing makespan for a given set of n jobs to be processed on each of m machines in a static jobshop, subject to the minimum completion time variance (CTV). A lower bound on CTV is developed for the static jobshop problem. A backward scheduling approach is proposed using the observations on the development of lower bound for hierarchical minimization of CTV and makespan. A lower bound on makespan subject to minimum CTV is also presented for this problem. Finally, we present two simulated annealing heuristic approaches using the concepts of forward and backward scheduling. Their performances are compared against each other through the use of the lower bounds established in this work. The simulated annealing heuristic based on backward scheduling is shown to perform well by evaluating the developed heuristics on 82 jobshop problems taken from literature. � 2005 Elsevier Ltd. All rights reserved.

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)

In the make-to-order (MTO) business model, manufacturing and outbound transportation are intimately linked due to little or no finished product inventory. Collaborative planning of the production and delivery is desired. This research seeks to explore a new collaborative scheduling method for production and distribution in supply chain for discrete manufacturing and distribution environment. A coordinated production and delivery scheduling problem, in which jobs are processed on a single batch processing machine (BPM) and then delivered to geographically dispersed customers, is addressed. The coordinated production and distribution model is applicable in many industries such as the integrated circuit (IC) burn-in process and delivery in the subcontract semiconductor assembly and test environment. Burn-in operation is operated in burn-in processor, which is considered as a type of batch processing machine in the semiconductor manufacturing. IC products after the burn-in operation are shipped to customers in different locations for the final test. In this thesis, two delivery methods, namely ‘Individual Delivery’ and ‘Batch Delivery’, are studied. For the ‘Individual Delivery’ method, a job after completion will be directly delivered to a customer. For the ‘Batch Delivery’ method, jobs completed on BPM will be delivered to multiple customers in batches. Especially, vehicle routing problem is considered in the batch delivery problem. Specifically, this thesis studies three subproblems: 1) coordinated production and individual and immediate delivery scheduling problem, 2) coordinated production and individual delivery scheduling problem with limited buffers, and 3) coordinated batch production and batch delivery problem with discrete split and vehicle routing. The objective of this research is to coordinate job schedule both on the production and distribution stages so as to minimize the time and cost related criteria. The objective functions studied in this research includes the makespan, delivery time and transportation cost. This research starts from the analysis of computational complexity of each problem. For those problems which are solvable, algorithms are developed in this research to obtain an optimal job schedule for the coordinated production and distribution problems. For those problems which are proved to be NP-hard, this research characterizes properties of optimal schedule. These optimal properties are beneficial to develop heuristic algorithms. Then both effective meta-heuristics and simple heuristics are designed to obtain promising job sequences. In particular, different efficient Differential Evolution algorithms combined with a dynamic programming algorithm, local search procedure or simple heuristics are developed in this thesis. Numerical experiments are conducted to evaluate the performance of proposed algorithms. Doctor of Philosophy (MAE)

Aircraft Engine Overhaul Divisions overhaul aero engines that have encountered unexpected failure during flight operation. The process of overhauling damaged parts sometimes doesn't involve only refurbishing damaged parts or component replacement, but also investigating into the root cause behind failure. It is mandated by aviation authorities to find out reasons behind an engine failure as flight safety has to be accounted for. In an Engine Overhaul Division (EOD) every engine needs to be overhauled within a certain fixed number of days or overhauling Tum Around Time (TAT). But when engines need to be repaired for certain failure and investigated into failure, the process can consume extra days from the fixed Engine Tum Around Time (TAT) without keeping up with the target. This delay can have an impact on engine availability for airline customers as airlines would have planned flight operations based on availability of engines. Delay or unavailability of engine can entail costs in terms of fleet management and also human factors, if a failure repeats itself leading to catastrophe. This also reflects on the productivity and competitiveness of the EOD. This study focuses on predicting the delay encountered by engines which have a specific repair and investigation requirement. The repair engines overhauled in an Engine Overhaul Division are classified into six groups based on similar failure symptoms. Based on past engine data, the delays in TAT of engines are calculated and suitable forecasting methods are identified to predict future delays. Two forecasting models, namely the Method of Moving Averages and Non Linear Grey Bernoulli method are used to generate suitable forecasts. Accuracy of the forecast is evaluated using error diagnostic Mean Absolute Percentage Error (MAPE). The results are compared between the actual recorded values and the predicted values generated by the forecasting methods. On comparing the results it was found that both forecasting methods have performed well with reasonable forecasting power. Also, one group of investigation demonstrated high MAPE possibly suggesting improper regrouping. Master of Science (Aerospace Engineering)

Customers have varying requirements on price and delivery time in make-to-order manufacturing environment. Due to limited availability of the production capacity, the firm can increase revenue if it allocates priority to time-sensitive customers, charging them a higher price for the same product. The remaining capacity can then be allocated amongst the price-sensitive customers with a relatively lower price. This strategy is aimed at maximizing the overall revenue for the firm. Moreover, the quoted price and delivery time have effects on the demand in the market. In literature, the demand function is considered as a linear decreasing function with respect to price and delivery time, respectively. The challenge is to coordinate the price quotation and the delivery time quotation for customers so that it results in maximizing the net revenue for a manufacturer. There are two types of capacity settings to differentiate products by price and delivery time. These are dedicated capacity and shared capacity. In the dedicated capacity, customers are categorized into several groups. Different customer groups are served in different production facilities. Customers from one customer group share a common price quotation and a common delivery time quotation. The common price and delivery time quotation problem is formulated for a single customer group. The optimality of this problem is studied and applied to develop an algorithm to find the optimal solution in polynomial time. Numerical examples show that the common price and delivery time quotation strategy is applicable when customers are more price-sensitive rather than time-sensitive. In the situation of shared capacity, all customers are served using the same production facility. The production priority is given to the customers who are more time-sensitive. Orders from the customers who are more price-sensitive are scheduled to the rear of the production sequence. Each customer will have a unique quotation of price and a unique quotation of delivery time. The problem is formulated and proven to be NP-complete even when prices are pre-determined parameters. A branch-and-bound algorithm is developed to obtain optimal solutions for the moderate-sized problem. Moreover, a heuristic algorithm is proposed to obtain the near-optimal solution in a short time. Numerical experiments are conducted to test the performance of these two methods. DOCTOR OF PHILOSOPHY (MAE)

In this thesis, the performance of various scheduling heuristics of a single serial processing machine with multiple job types in the semiconductor assembly test environment is analyzed. Two types of heuristics are developed in this research. The heuristic with next arrival information is compared with the heuristic without future information to study how the performance is influenced by forecast. Considering the dynamic manufacturing characteristics of the semiconductor industry, the impact of different level of forecast error is analyzed under different traffic intensities. Two sets of heuristics are tested in simulations to demonstrate that the performance of a model with future information highly depends on how the forecast information is utilized in the heuristics. ​Master of Science (IMST)

Although microfluidic technology is at its infancy stage, it offers many advantages for disease screening. In this thesis, our focus is to develop the supply chain strategies for serving the elusive pandemic demand in Singapore. To make the supply chain more robust, a few opportunities for delayed differentiation are identified. Next, demand-capacity evaluations for pandemic disease screening device were performed which suggests that the pandemic demand in Singapore is too low to warrant the establishment of a dedicated production facility. If a production facility is to be built, a possible business model could be to produce normal blood testing kits and reserved some capacity to satisfy the pandemic demand. Several production options are then discussed and that the production facility is advised to choose the option which can bring the highest expected profit. ​Master of Science (IMST)

An effective production strategy would lead to efficient production line performance as well as increased profit. However, there is no fixed or generalized solution. In this project, the author treat the n-job, two-stage hybrid flow line problem with 2 different machines in the first station and 7 identical machines in the second station. The objective for this project is to reducing the total cost. The author researched the ways to improve a company’s performance by reducing the total cost from four different aspects (Production batches, transfer batches, dedicated line as well as predetermining a shared product type). After this project, the total estimated saving for company will be S$18988.6 per 42 weeks, which is over 10% of total cost. The research is meaningful and can provide a guide for manufacturing industry. ​Master of Science (IMST)

Very little research have considered the combined aspects of scheduling involving (i) a dynamic and stochastic shop floor, (ii) Sequence-Dependent Setup (SDS), (iii) transportation, and (iv) the consideration of user preferences to achieve the best/preferred trade-offs amongst the multiple contradicting objectives. Given these complexities, it is indeed challenging to determine when and how the next task (i.e. transportation, setup, processing of a lot) should be selected and executed on each machine such that the best/preferred trade-offs amongst the multiple conflicting objectives can be achieved based on user preferences in an online, near-real-time manner. In this research, the NEXt Task Scheduling (NEXTS) methodology, made up of a NEXTS time policy and a NEXTS decision policy, is proposed. The NEXTS time policy specifies when to schedule. In essence, the time policy stipulates the appropriate timing (i.e. before and as close as possible to the time when the machine is available) for the selection and transportation of the next lot. The NEXTS decision policy specifies how a scheduling decision is to be made. The decision policy is made up of a multiobjective rule (i.e. weighted aggregation of dispatching criteria/rule) that is applied for the selection of the next lot and a Look Ahead Simulation-based Genetic Algorithm with Desirability function (LASGAD) that optimizes the weights used in the multiobjective rule in accordance with user preferences. The multiple performance measures of interest in this research are average cycle time, standard deviation of cycle time, average tardiness, and standard deviation of tardiness. The NEXTS time policy is shown to perform better than the existing Periodic Scheduling/Rescheduling and dispatching time policies when there are transportation and decision making times involved. Simulation results also show that on-line LASGAD is better at finding the optimal set of weights than the off-line response surface methodology with desirability function method. The novel NEXTS methodology contributes to the advancement of knowledge by making use of real-time data for effective on-line scheduling of a dynamic and stochastic shop floor with sequence-dependent setups, transportation times, and user specified preferences to obtain Pareto optimal performance in the face of multiple conflicting objectives. DOCTOR OF PHILOSOPHY (MAE)

A transportation network for employees at a local company faced problems with unbalanced utilization and passenger complains caused by occasional overcrowding in vehicles. The objective of this work was to develop a method for planning transportation routes and establish its reliability in consistently delivering a near or optimal solution. Two models were built each with a different Integer programming formulation- Formulation I and II. Formulation I consists of vehicle cost and penalty cost components in its objective function so that the optimal solution would balance actual cost and passenger service level. The model was implemented in the EXCELbased Risk Solver Platform but could not find a feasible solution for even a small set of 4-node problem. Formulation II, built upon experience from the first model, had an improved cost function that excluded the penalty cost component. An implementation in XPRESS-MP and subsequent verification with enumeration solutions proved its ability to solve both the 3-node and 4-node problems to optimality. A profile of objective value over various vehicle capacity values served as a guide to setting passenger service level. The XPRESS-MP model was implemented in Stage II of this work on a 13-node problem based on actual data. The solution was compared with manually generated routes and was found to outperform the latter by at least 9%. Even with passenger service level imposed on the model, a 5% cost saving was attained. Proactive efforts in data collection and maintenance are encouraged to ensure successful full scale implementation of this model in the future. ​Master of Science (IMST)

This project investigates a production line that faces fluctuating demand with seasonal pattern. The cumulative capacity exceeds the cumulative demand in a one year period; however, its expected weekly capacity is not able to meet the weekly demand during the peak season. In addition, examining its past production outputs, there existed a large gap below the expected capacity. Therefore, it has become crucial to study the significant factors influencing the line performance. ​Master of Science (IMST)

This project aims to study the effects of open-loop and closed loop job release policies and dispatching rules in an electrical appliance company in Singapore. While maintaining the throughput at the required level with high utilization rate, the project aims to reduce the work-in-process inventory level, as well as to reduce average cycle time, cycle time standard deviation and thus system variability. The developed models and solution methods are validated using actual production data and the results are compared among each other and against the current performance. ​Master of Science (IMST)

In PCB Assembly manufacturing environment, there are usually three objectives to achieve – minimizing setup cost, minimizing average cycle time, and minimizing job lateness. With the re-entrant trait of PCB Assembly system, scheduling job release is a complicated but crucial problem which plays an important role in improving the whole factory performance, maximizing factory production capability, minimizing waste and maximizing revenue. How to schedule jobs with dynamic queue to achieve the three objectives is where we focus on. ​Master of Science (IMST)

As an emerging industry, microfluidic device manufacturing has little large scale production experience. Many areas, like base materials selection, mass production processes and equipment design, have not been well established. The uncertainties bring both challenges and opportunities. If we are able to anticipate the potential production system related problems proactively, it will greatly help the research and development better realize the concept of design-for-manufacturing and prepare us to accelerate fast once the large scale production takes place. In this thesis project, we began with characterization of polymer based microfluidic manufacturing processes. A probable production flow was constructed for relatively simple devices and extended to represent more complicated and generic systems. The potential challenges in the production planning were discussed and corresponding recommendations were made on process development and equipment designs. ​Master of Science (IMST)

Many businesses have been focusing on two priorities in their manufacturing systems in recent years - cost and quality. In order to achieve these key priorities, organizations are adopting various business improvement methodologies such as six sigma, lean manufacturing, cost reduction, business process re-engineering, total quality management, etc. ​Master of Science (IMST)

To stay competitive in the booming rig-building industry and era, world leading rigdesigner and builder like Keppel Offshore and Marine endeavors to manage the construction resource in a scientific way to cut cost and improve operation efficiency. Although a leader in operation and manufacturing excellence, it is eager to exploit room for management improvement in the areas of painting operation resource, scaffolding resource and manpower resource. ​Master of Science (IMST)

Due to the volatility of market demand, short product lifecycle, long manufacturing lead-time and huge capital investment in semiconductor industry, planning becomes an increasingly challenging task to perform. ​Master of Science (IMST)

In today's cost driven semiconductor industry, utilizing the available capacity to its maximum limits is of prime importance for being competitive. With the equipments being expensive and the technology changing very fast, utilization of the available resources, by minimizing the repair time brings to the forefront production capacity that would have otherwise stayed hidden or lost. The other key issue that any company needs to address is that repairing complicated machines (such as Wire Bond) requires training of personnel and this leads to extra costs. Thus a system was felt necessary that would incorporate the knowledge base of the most skilled maintenance engineers and also aid in online breakdown diagnosis, so as to reduce MTTR. The e-Diagnostics system that has been developed as a part of this project aims at making a wholesome online diagnostics tool. This e-Diagnostics system also aims to centralize the database of all the wire bonding machines, thus easing the access of information and providing key information, that would otherwise require another tool such as data mining. This system would hence provide a long-term solution to the company, as it can be modified to serve machines other than Wire Bonding machines. ​Master of Science (IMST)

Today's industrial environment is becoming more and more volatile and product life cycles are getting shorter. In this scenario, it becomes very important for companies to reexamine their supply chain and to do effective operational planning. The following thesis proposes scientific methodologies to look at some issues of the supply chain such as Capacity Planning, Production and Procurement Planning. The performance of supply chain is limited by capacity constraints on the system. Hence, it becomes vital to plan capacity wisely in anticipation of certain demand. The thesis presents an effective method for planning capacity in terms of equipment selection and resource allocation. The next stage after Capacity Planning is that of production itself and various tactical modes for production management are suggested. One model utilizes a fast transportation mode to reduce lead-time while the other model tries to compensate for the obsolescence cost by introducing the concept of obsolescence risk. The high fluctuation in demand also gives rise to the need of an effective procurement plan so as to minimize excess and obsolescence costs. The amount of safety stock that needs to be set in such a sienario is presented, as inventory costs are a significant contribution to the excess costs incurred. The focus is on making the entire system more flexible at the minimum cost. ​Master of Science (IMST)

This project studies the different facets of the semiconductor backend manufacturing industry. The author looked into manufacturing systems issues, e-Business, state-of-the-art developments in semiconductor test operations and equipment, and emerging techniques in semiconductor product development. Master of Science

Computer simulations and modeling have become a popular analysis technique to achieve the objectives of shortening cycle time and increasing resources' utilization and production throughput in manufacturing companies. Being able to model and analyze the dynamic characteristics of existing shopfloor activities, and being able to predict the behavior of shopfloor activities prior to the actual implementation of decisions will enable companies to plan and control their constrained resources. Furthermore, by evaluating the flow of raw materials and parts through workstations and examining the conflicting demands for limited resources, companies will be able to evaluate the physical layouts of shopfloor, equipment selection and operating procedures more effectively. Master of Science (Computer Integrated Manufacturing)

This is a report describing the designing, planning and implementation for an automated real-time data collection system relating to equipment efficiency. The system is to be implemented in the operations area of a semiconductor company[l]. The work reported will form the foundation for planning and implementing subsequent phases of the corporate wide C1M architecture. The thesis begins with the explanation of the equipment efficiency, data collection and its relevance in the industry. An overview of the company, with the current architecture is provided. This is followed by an explanation of the new corporate architecture and the proposed system. System design, integration and implementation plans are discussed in detail. The thesis ends with the discussion chapter where the implications of implementing this system in the company are elaborated. Master of Science (Computer Integrated Manufacturing)