In this thesis we have presented a mathematical model of a scheduling problem which arises in the Brewing Industry. We have implemented two different types of global optimization algorithms to find the global minimum of the problem. Several instances of the scheduling problem are considered and the results thereof are presented. The results show that significant savings can be made if the global optimization techniques are used in brewery Industry.

Neste trabalho será estudado um ambiente de produção que é freqüentemente encontrado na prática: o flowshop com múltiplos processadores. No caso estudado existem estágios em série e em cada estágio existe um número de máquinas idênticas em paralelo. Todas as tarefas devem ser processadas por todos os estágios. O objetivo é minimizar o atraso das tarefas. Primeiramente o problema foi abordado através de um método que programa as tarefas por estágio e em ordem direta, ou seja, do primeiro para o último estágio. Em seguida, foram desenvolvidas duas novas regras que utilizam o mesmo método de programação, porém consideram o ambiente como uma série de problemas de máquinas em paralelo. Uma das regras desenvolvidas tem como característica principal considerar estados futuros do sistema. Também foi desenvolvido um novo método de programação em ordem inversa, no qual as tarefas são programadas do último para o primeiro estágio. Este método apresenta melhor desempenho se comparado com o método de programação em ordem inversa da literatura. Por último foi desenvolvido um método de programação com foco no estágio gargalo, visto que este estágio pode impedir um bom fluxo das tarefas pelo sistema e resultar em uma conclusão tardia das mesmas. Este método é mais simples, rápido e tem resultados competitivos frente ao método com foco no gargalo da literatura. / This work considers a production environment that is frequently found in practice: the flexible flowshop. In the case studied, there are stages in series and in each stage there are a number of identical parallel machines. All jobs must be processed by all stages. The objective is to minimize the tardiness of jobs. First the problem was addressed by a method in which jobs are schedule forward, that is, from first to last stage. Two new rules were developed using this same method, but considering the environment as a series of parallel machines problems. One of the rules is able to consider future states of the system. It was also developed a new method in which jobs are scheduled backward, i.e., from last to first stage. This method shows better performance compared to the literature method. At last, it was developed a method that focus on the bottleneck stage scheduling (since this stage may prevent a good flow of jobs throughout the system and result in late completions). This method is simpler, faster and competitive next to the literature method.

Wire Bonder and Molding are the most costive equipments in the investment of IC packaging; and the packaging quality, cost and delivery are concerned most in the assembly processes. An inappropriate process scheduling may result in the wastes of resources and assembly bottleneck. Manager must allocate the resources appropriately to adapt the changeable products and production lines. We would introduce several heuristic search methods, especially the Tabu search. Tabu search is one of the most popular methods of heuristic search. We also use Tabu list to record several latest moves and avoid to the duplication of the paths or loops. It starts from an initial solution and keep moving the solution to the best neighborhood without stock by Tabu. The iterations would be repeated until the terminating condition is reached. At last of the report, an example will be designed to approach the best wire bonding and molding scheduling by Tabu search; and verify the output volume is more than those with FIFO in the same period of production time. Tabu search will be then confirmed to be effective for flexible flow shop.

abstract: A good production schedule in a semiconductor back-end facility is critical for the on time delivery of customer orders. Compared to the front-end process that is dominated by re-entrant product flows, the back-end process is linear and therefore more suitable for scheduling. However, the production scheduling of the back-end process is still very difficult due to the wide product mix, large number of parallel machines, product family related setups, machine-product qualification, and weekly demand consisting of thousands of lots. In this research, a novel mixed-integer-linear-programming (MILP) model is proposed for the batch production scheduling of a semiconductor back-end facility. In the MILP formulation, the manufacturing process is modeled as a flexible flow line with bottleneck stages, unrelated parallel machines, product family related sequence-independent setups, and product-machine qualification considerations. However, this MILP formulation is difficult to solve for real size problem instances. In a semiconductor back-end facility, production scheduling usually needs to be done every day while considering updated demand forecast for a medium term planning horizon. Due to the limitation on the solvable size of the MILP model, a deterministic scheduling system (DSS), consisting of an optimizer and a scheduler, is proposed to provide sub-optimal solutions in a short time for real size problem instances. The optimizer generates a tentative production plan. Then the scheduler sequences each lot on each individual machine according to the tentative production plan and scheduling rules. Customized factory rules and additional resource constraints are included in the DSS, such as preventive maintenance schedule, setup crew availability, and carrier limitations. Small problem instances are randomly generated to compare the performances of the MILP model and the deterministic scheduling system. Then experimental design is applied to understand the behavior of the DSS and identify the best configuration of the DSS under different demand scenarios. Product-machine qualification decisions have long-term and significant impact on production scheduling. A robust product-machine qualification matrix is critical for meeting demand when demand quantity or mix varies. In the second part of this research, a stochastic mixed integer programming model is proposed to balance the tradeoff between current machine qualification costs and future backorder costs with uncertain demand. The L-shaped method and acceleration techniques are proposed to solve the stochastic model. Computational results are provided to compare the performance of different solution methods. / Dissertation/Thesis / Ph.D. Industrial Engineering 2011

Neste trabalho será estudado um ambiente de produção que é freqüentemente encontrado na prática: o flowshop com múltiplos processadores. No caso estudado existem estágios em série e em cada estágio existe um número de máquinas idênticas em paralelo. Todas as tarefas devem ser processadas por todos os estágios. O objetivo é minimizar o atraso das tarefas. Primeiramente o problema foi abordado através de um método que programa as tarefas por estágio e em ordem direta, ou seja, do primeiro para o último estágio. Em seguida, foram desenvolvidas duas novas regras que utilizam o mesmo método de programação, porém consideram o ambiente como uma série de problemas de máquinas em paralelo. Uma das regras desenvolvidas tem como característica principal considerar estados futuros do sistema. Também foi desenvolvido um novo método de programação em ordem inversa, no qual as tarefas são programadas do último para o primeiro estágio. Este método apresenta melhor desempenho se comparado com o método de programação em ordem inversa da literatura. Por último foi desenvolvido um método de programação com foco no estágio gargalo, visto que este estágio pode impedir um bom fluxo das tarefas pelo sistema e resultar em uma conclusão tardia das mesmas. Este método é mais simples, rápido e tem resultados competitivos frente ao método com foco no gargalo da literatura. / This work considers a production environment that is frequently found in practice: the flexible flowshop. In the case studied, there are stages in series and in each stage there are a number of identical parallel machines. All jobs must be processed by all stages. The objective is to minimize the tardiness of jobs. First the problem was addressed by a method in which jobs are schedule forward, that is, from first to last stage. Two new rules were developed using this same method, but considering the environment as a series of parallel machines problems. One of the rules is able to consider future states of the system. It was also developed a new method in which jobs are scheduled backward, i.e., from last to first stage. This method shows better performance compared to the literature method. At last, it was developed a method that focus on the bottleneck stage scheduling (since this stage may prevent a good flow of jobs throughout the system and result in late completions). This method is simpler, faster and competitive next to the literature method.

由於網際網路的發展，使得全球環境變遷，競爭越來越激烈，企業必須面臨快速的需求變化，以及訂單履行時間縮短的問題，因此如何有效的利用生產規劃和現場排程來幫助企業達到較高的訂單達成率和即時反應現場產能一直是製造業努力的目標。 在排程的問題中，用派工法則來解決排程問題的工廠類型，主要集中在零工式生產系統及流程式生產系統，而進一步加入平行機器概念，即是彈性零工式生產及彈性流程式生產。而現在許多的服務業也都是屬於彈性流程式生產的模式，而且還具有迴流(recirculation)之性質，而之前使用在不具迴流性質之彈性流程式生產的派工法則，在具有迴流性質之彈性流程式生產中是否仍然可以表現良好，是值得探討的。然而更進一步在此具有迴流性質之彈性流程式生產中加入多工的性質，使工作可以被兩個或兩個以上的機器或操作人員進行處理，則運用哪個派工法則讓機器或操作人員選擇工作來進行處理，可以使得選定的目標值有良好的表現，是相當值得研究之問題。 / As information technology advances, whole world environmental trend and the competition is more and more intense. The enterprise must face faster demand changes and the problem of shorter order fulfillment. Therefore, how to apply efficient production planning and shop floor scheduling to attain a better order fulfillment and real time production of shop floor capacity is the goal enterprises strive toward. The shop floor scheduling problems using dispatching rules to solve are focus on job shop scheduling problems and flow shop scheduling problems. Moreover, those problems adding the concept of parallel machine will change into flexible job shop scheduling problems and flexible flow shop scheduling problems. Many service industries also belong to this type. In addition, those service industries’ processes also contain the important characteristic of recirculation. Now, there are two problems I would like to solve. First, Whether the dispatching rules which can get good results in flexible flow shop scheduling problems will also get good results in flexible flow shop scheduling problems with recirculation. Second, I add the characteristic of parallel machine into my problem, so it means jobs in the process can be operated by two or more workers. Therefore, which dispatching rule will get better results based on chosen achievement targets in the problem is very interesting to research.