Dissertations / Theses on the topic 'Permutacional Flowshop Scheduling Problem'

CoordenaÃÃo de AperfeiÃoamento de NÃvel Superior
Neste trabalho foram tratados dois problemas: o primeiro à denominado Continuous Permutation Flowshop Scheduling Problem (CPFSP), que possui a restriÃÃo de que nenhuma tarefa pode esperar por processamento entre mÃquinas consecutivas; o segundo à denominado de Permutation Flowshop Scheduling Problem (PFSP), em que a restriÃÃo anterior nÃo existe. A metaheurÃstica Algoritmo GenÃtico (AG) tem sido aplicada com sucesso ao PFSP, mas atà o momento nÃo foi encontrado na literatura algo que mostre que o AG à um bom mÃtodo para o CPFSP. O objetivo deste trabalho foi desenvolver um AG eficiente paras esses dois problemas, mas que nÃo precisa utilizar inicializaÃÃo eficiente e/ou hibridizaÃÃo com outra tÃcnica de busca. O desenvolvimento do AG proposto levou em consideraÃÃo as caracterÃsticas, diversificaÃÃo e a intensificaÃÃo, que inspiraram a criaÃÃo de trÃs procedimentos que melhoraram o desempenho do AG proposto. Foram realizados vÃrios experimentos com as instÃncias de Taillard (1993), Reeves (1995) e Heller (1960). Os resultados foram comparados com outros mÃtodos encontrados na literatura. Foram construÃdos polinÃmios com a utilizaÃÃo de InterpolaÃÃo Lagrangeana para determinar o tempo execuÃÃo do AG proposto. Por fim, o mÃtodo foi aplicado num problema real. Os resultados mostraram que o AG proposto à o melhor mÃtodo para o CPFSP e que fica muito prÃximo do melhor AG encontrado na literatura com inicializaÃÃo eficiente para o PFSP

In cellular manufacturing systems, minimization of the completion time has a great impact on the production time, material flow, and productivity. An effective scheduling is crucial to attaining the advantages of cellular manufacturing systems. This dissertation attempts to solve the Flowshop Manufacturing Cell (cellular flowshop) Scheduling Problem with Sequence Dependent Setup Times (FMCSP with SDSTs) considering two performance measures: the total flow time as a mono objective, and the makespan and total flow time combined as a bi-criteria scheduling problem. The proposed problem is known to be the NP-hard problem because of its complexity. Several metaheuristic algorithms based on Genetic Algorithm (GA), Simulated Annealing (SA), and Particle Swarm Optimization (PSO) are developed for scheduling part families as well as jobs within each part family for FMCSP with SDSTs to minimize the total flow time. A local search method based on SA combined with PSO (named as PSO-SA) is proposed to enhance the intensification and improve the quality of the solution obtained by pure PSO. The effectiveness and efficiency of the proposed metaheuristics are evaluated based on the Relative Percentage Deviation (RPD) from its lower bound, and the robustness. Results indicate PSO-SA is performed similar to best available algorithms for small and medium size test problems. Yet, there is a very small deviation from best results for large problems. A Multi-objective Particle Swarm Optimization (MPSO) and a Multi-objective Simulated Annealing (MOSA) Algorithm are further proposed to solve the bi-criteria optimization problem to minimize the total flow time and makespan simultaneously. An improved PSO is combined with Threshold Acceptance (TA) algorithm to improve effectiveness of the proposed MPSO (named as IMPSO-TA) for the convergence of the obtained Pareto Front. The proposed algorithms are evaluated using several Quality Indicators (QI) measures for multiobjective optimization problems. The proposed algorithms can generate approximated Pareto Fronts in a reasonable CPU time. The proposed IMPSO-SA outperforms MOSA algorithm in terms of CPU time and minimizing the objective functions.
October 2015

[EN] Nowadays, manufacturing systems meet different new global challenges and the existence of a collaborative manufacturing environment is essential to face with. Distributed manufacturing and assembly systems are two manufacturing systems which allow industries to deal with some of these challenges. This thesis studies a production problem in which both distributed manufacturing and assembly systems are considered. Although distributed manufacturing systems and assembly systems are well-known problems and have been extensively studied in the literature, to the best of our knowledge, considering these two systems together as in this thesis is the first effort in the literature. Due to the importance of scheduling optimization on production performance, some different ways to optimize the scheduling of the considered problem are discussed in this thesis. The studied scheduling setting consists of two stages: A production and an assembly stage. Various production centers make the first stage. Each of these centers consists of several machines which are dedicated to manufacture jobs. A single assembly machine is considered for the second stage. The produced jobs are assembled on the assembly machine to form final products through a defined assembly program. In this thesis, two different problems regarding two different production configurations for the production centers of the first stage are considered. The first configuration is a flowshop that results in what we refer to as the Distributed Assembly Permutation Flowshop Scheduling Problem (DAPFSP). The second problem is referred to as the Distributed Parallel Machine and Assembly Scheduling Problem (DPMASP), where unrelated parallel machines configure the production centers. Makespan minimization of the product on the assembly machine located in the assembly stage is considered as the objective function for all considered problems. In this thesis some extensions are considered for the studied problems so as to bring them as close as possible to the reality of production shops. In the DAPFSP, sequence dependent setup times are added for machines in both production and assembly stages. Similarly, in the DPMASP, due to technological constraints, some defined jobs can be processed only in certain factories. Mathematical models are presented as an exact solution for some of the presented problems and two state-of-art solvers, CPLEX and GUROBI are used to solve them. Since these solvers are not able to solve large sized problems, we design and develop heuristic methods to solve the problems. In addition to heuristics, some metaheuristics are also designed and proposed to improve the solutions obtained by heuristics. Finally, for each proposed problem, the performance of the proposed solution methods is compared through extensive computational and comprehensive ANOVA statistical analysis.
[ES] Los sistemas de producción se enfrentan a retos globales en los que el concepto de fabricación colaborativa es crucial para poder tener éxito en el entorno cambiante y complejo en el que nos encontramos. Una característica de los sistemas productivos que puede ayudar a lograr este objetivo consiste en disponer de una red de fabricación distribuida en la que los productos se fabriquen en localizaciones diferentes y se vayan ensamblando para obtener el producto final. En estos casos, disponer de modelos y herramientas para mejorar el rendimiento de sistemas de producción distribuidos con ensamblajes es una manera de asegurar la eficiencia de los mismos. En esta tesis doctoral se estudian los sistemas de fabricación distribuidos con operaciones de ensamblaje. Los sistemas distribuidos y los sistemas con operaciones de ensamblaje han sido estudiados por separado en la literatura. De hecho, no se han encontrado estudios de sistemas con ambas características consideradas de forma conjunta. Dada la complejidad de considerar conjuntamente ambos tipos de sistemas a la hora de realizar la programación de la producción en los mismos, se ha abordado su estudio considerando un modelo bietápico en la que en la primera etapa se consideran las operaciones de producción y en la segunda se plantean las operaciones de ensamblaje. Dependiendo de la configuración de la primera etapa se han estudiado dos variantes. En la primera variante se asume que la etapa de producción está compuesta por sendos sistemas tipo flowshop en los que se fabrican los componentes que se ensamblan en la segunda etapa (Distributed Assembly Permutation Flowshop Scheduling Problem o DAPFSP). En la segunda variante se considera un sistema de máquinas en paralelo no relacionadas (Distributed Parallel Machine and Assembly Scheduling Problem o DPMASP). En ambas variantes se optimiza la fecha de finalización del último trabajo secuenciado (Cmax) y se contempla la posibilidad que existan tiempos de cambio (setup) dependientes de la secuencia de trabajos fabricada. También, en el caso DPMASP se estudia la posibilidad de prohibir o no el uso de determinadas máquinas de la etapa de producción. Se han desarrollado modelos matemáticos para resolver algunas de las variantes anteriores. Estos modelos se han resuelto mediante los programas CPLEX y GUROBI en aquellos casos que ha sido posible. Para las instancias en los que el modelo matemático no ofrecía una solución al problema se han desarrollado heurísticas y metaheurísticas para ello. Todos los procedimientos anteriores han sido estudiados para determinar el rendimiento de los diferentes algoritmos planteados. Para ello se ha realizado un exhaustivo estudio computacional en el que se han aplicado técnicas ANOVA. Los resultados obtenidos en la tesis permiten avanzar en la comprensión del comportamiento de los sistemas productivos distribuidos con ensamblajes, definiendo algoritmos que permiten obtener buenas soluciones a este tipo de problemas tan complejos que aparecen tantas veces en la realidad industrial.
[CAT] Els sistemes de producció s'enfronten a reptes globals en què el concepte de fabricació col.laborativa és crucial per a poder tindre èxit en l'entorn canviant i complex en què ens trobem. Una característica dels sistemes productius que pot ajudar a aconseguir este objectiu consistix a disposar d'una xarxa de fabricació distribuïda en la que els productes es fabriquen en localitzacions diferents i es vagen acoblant per a obtindre el producte final. En estos casos, disposar de models i ferramentes per a millorar el rendiment de sistemes de producció distribuïts amb acoblaments és una manera d'assegurar l'eficiència dels mateixos. En esta tesi doctoral s'estudien els sistemes de fabricació distribuïts amb operacions d'acoblament. Els sistemes distribuïts i els sistemes amb operacions d'acoblament han sigut estudiats per separat en la literatura però, en allò que es coneix, no s'han trobat estudis de sistemes amb ambdós característiques conjuntament. Donada la complexitat de considerar conjuntament ambdós tipus de sistemes a l'hora de realitzar la programació de la producció en els mateixos, s'ha abordat el seu estudi considerant un model bietàpic en la que en la primera etapa es consideren les operacions de producció i en la segona es plantegen les operacions d'acoblament. Depenent de la configuració de la primera etapa s'han estudiat dos variants. En la primera variant s'assumix que l'etapa de producció està composta per sengles sistemes tipus flowshop en els que es fabriquen els components que s'acoblen en la segona etapa (Distributed Assembly Permutation Flowshop Scheduling Problem o DAPFSP). En la segona variant es considera un sistema de màquines en paral.lel no relacionades (Distributed Parallel Machine and Assembly Scheduling Problem o DPMASP). En ambdós variants s'optimitza la data de finalització de l'últim treball seqüenciat (Cmax) i es contempla la possibilitat que existisquen temps de canvi (setup) dependents de la seqüència de treballs fabricada. També, en el cas DPMASP s'estudia la possibilitat de prohibir o no l'ús de determinades màquines de l'etapa de producció. S'han desenvolupat models matemàtics per a resoldre algunes de les variants anteriors. Estos models s'han resolt per mitjà dels programes CPLEX i GUROBI en aquells casos que ha sigut possible. Per a les instàncies en què el model matemàtic no oferia una solució al problema s'han desenrotllat heurístiques i metaheurísticas per a això. Tots els procediments anteriors han sigut estudiats per a determinar el rendiment dels diferents algoritmes plantejats. Per a això s'ha realitzat un exhaustiu estudi computacional en què s'han aplicat tècniques ANOVA. Els resultats obtinguts en la tesi permeten avançar en la comprensió del comportament dels sistemes productius distribuïts amb acoblaments, definint algoritmes que permeten obtindre bones solucions a este tipus de problemes tan complexos que apareixen tantes vegades en la realitat industrial.
Hatami, S. (2016). The Distributed and Assembly Scheduling Problem [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/64072
TESIS

Estimation of Distribution Algorithm (EDA) is a branch of evolutionary computation that learn a probabilistic model of good solutions. Probabilistic models are used to represent relationships between solution variables which may give useful, human-understandable insights into real-world problems. Also, developing an effective PM has been shown to significantly reduce function evaluations needed to reach good solutions. This is also useful for real-world problems because their representations are often complex needing more computation to arrive at good solutions. In particular, many real-world problems are naturally represented as permutations and have expensive evaluation functions. EDAs can, however, be computationally expensive when models are too complex. There has therefore been much recent work on developing suitable EDAs for permutation representation. EDAs can now produce state-of-the-art performance on some permutation benchmark problems. However, models are still complex and computationally expensive making them hard to apply to real-world problems. This study investigates some limitations of EDAs in solving permutation and scheduling problems. The focus of this thesis is on addressing redundancies in the Random Key representation, preserving diversity in EDA, simplifying the complexity attributed to the use of multiple local improvement procedures and transferring knowledge from solving a benchmark project scheduling problem to a similar real-world problem. In this thesis, we achieve state-of-the-art performance on the Permutation Flowshop Scheduling Problem benchmarks as well as significantly reducing both the computational effort required to build the probabilistic model and the number of function evaluations. We also achieve competitive results on project scheduling benchmarks. Methods adapted for solving a real-world project scheduling problem presents significant improvements.

Cette thèse traite des lignes de traitement de surface qui sont des lignes dans lesquelles les pièces sont immergées dans une succession de cuves. Chaque cuve contient des bains qui affectent les propriétés mécaniques ou électriques des pièces. Ce type de ligne est utilisé, par exemple, pour la galvanoplastie. Les pièces sont montées sur des porteurs et transportées d'une cuve à l'autre par un robot. Le temps opératoire (ou temps pendant lequel la pièce reste dans la cuve) est borné. La borne inférieure est le temps minimum qui permet le traitement et la borne supérieure dépend du type de traitement (attaque acide, rinçage...).
Un objectif classique est de trouver les mouvements du robot qui maximisent la productivité, ce problème est communément appelé “hoist scheduling problem” (HSP). Lors de ce travail nous nous sommes attachés à une production cyclique. Nous avons proposé dans le cas d'une ligne à deux cuves une méthode permettant d'obtenir les cycles optimaux. Nous avons démontré, pour le cas d'une ligne équilibrée à trois cuves pour une production mono-produit, les caractéristiques des cycles optimaux ainsi qu'une méthode pour les obtenir. Ensuite, nous avons étudié le problème sur quatre machines dans le cas où les temps de trempe sont égaux et sans attente. Nous avons proposé les cycles optimaux dans le cas d'une production mono-produit. Enfin nous avons proposé une conjecture sur les cycles optimaux et en avons démontré certaines parties, dans le cas d'une ligne équilibrée avec un nombre de cuves quelconque et où les marges sur les temps de process sont nulles.

博士
國立清華大學
工業工程研究所
82
Since Johnson, in his pioneering work, proposed a polynominal time algorithm for the two-machine flowshop scheduling problem. The flowshop scheduling problems have been studied extensively. However, due to the simplicity of the convertional models, they can not be successfully implemented in some practical scheduling problem with reprocessing operations, the scheduling problem with limited waiting time constraints, the scheduling problem with processing time linearly dependent on job waitting- time. These extensions have some practical applications in bridge construction , semiconductor manufacturing, metallurgical process, food production and chemical industry. We show that these problems are Np-hard. We also derive some theoretical results and propose some efficient algorithms for solving them.

碩士
國立勤益科技大學
工業工程與管理系
97
This paper explores the Pareto optimal solutions for solving multi-objective combinatorial optimization problems. It is necessary to consider the convergence and diversity. This paper proposes a heuristic, LH algorithm, based on Genetic algorithm (GA) for flowshop scheduling problem with multiple objectives of minimizing makespan, total tardiness and total flow time. The algorithm can provide efficient Pareto optimal solutions for decision makers’ reference. Firstly, it refers NEH and modified NEH algorithms to produce several good initial solutions. For searching the whole solution space, the paper applies the gradual-priority weighting approach to determine the objective function and fitness value. Meanwhile, the algorithm avoids the generation converge too early, so presents an intensification mechanism of some new solutions generation. This paper constructs three solution sets to record three objectives individually. The experimental results show that the proposed algorithm can find more effective solutions than an existed GA-based algorithm. The related error percentages of individual objective and combined objectives are superior.

碩士
國立勤益科技大學
工業工程與管理系
97
Several production lines are hybrid flowshop, which are mixed two production systems of flowshop and parallel machines. The machine preventive maintenance or adjustment is needed in a specified period of time, therefore the machine is not available. The two-stage hybrid flowshop includes several machines in each stage and preventive maintenance or adjustment us considered. The paper proposes a heuristic based on gentic algorithm (GA), named GA_H algorithm to minimize makespan.The initial solution of GA_H algorithm are combination JR、SPT、NEH、NEH_R(r) algorithm and LPT, FAM rules. The paper selects some excellent solution to reproduce the next generation through adaptive selection、crossover and mutation. In order to avoid premature convergence in search procedure, a restart mechanism is used to explore a new solution region. The experimental results show that GA_H algorithm is better than MLJLF algorithm, and the ARP and ARPLB are 3.02% and 1.31%, respectively. The performance of GA_H algorithm is superity.

碩士
逢甲大學
工業工程學系
88
In past, while studying the flowshop scheduling problem, it is generally assumed that all jobs are equal in importance. In reality, such an assumption need not necessarily hold. For example, jobs have different unit costs and holding costs, and hence they cannot be treated equivalently. In order to solve the problem, in this paper, we study the flowshop scheduling problem with respect to minimizing the total weighted flowtime of jobs. Genetic algorithm has been used widely in many fields and proved of good effect. Some scholars point out that combine genetic algorithm and conventional heuristics often outperform either method operating alone. In this paper, we focus on encoding and individual searching to develop a hybrid genetic algorithm for the flowshop scheduling problem.

碩士
朝陽科技大學
工業工程與管理系碩士班
94
Abstract The flowshop scheduling problem can be stated as follows. There are n independent jobs and m different machines. There is a common restriction on the order in which the operations of a job are to be performed. Each machine can process at most one job at a time and each job can be processed on one machine at a time. Flowshop scheduling is often encountered in mass production systems. Scheduling problems with no-wait constraints occur in many industries. For instance, in hot metal rolling industries , where the heated metal has to undergo a series of operations at continuously high temperatures before it is cooled in order to prevent defects. Similarly , in the plastic molding and silverware production industries, a series of operations must be performed to immediately follow one another to prevent degradation. We consider the performance measure of total tardinesss in a two-machine no-wait flow shop environment. In our research, we present a heuristic solution method for solving large-scaled problems. We also develop a branch and bound algorithm. We use an upper bound based on the heuristic algorithm developed, and propose some dominance rules to help pruning unpromising nodes in the branch-and-bound search tree. Finally, computational experiments are conducted to evaluate the performances of the proposed algorithms. As the result, branch-and-bound algorithm can only solve to the optimum solution small-scaled problems. When the number of jobs equals to 25, the average error of heuristic solution is 6%. The average error of lower bound is about 11%. The developed dominance rules help reducing 16%~20% nodes in the branch-and-bound search tree. Besides, our research examines two special cases of bottleneck-machine. It is showed that both heuristic solution and lower bound coincide with the optimum solution in great majority problems with bottleneck-machine. Therefore, problems with bottleneck-machine become easier to solve.

碩士
臺中技術學院
資訊科技與應用研究所
97
The permutation flowshop scheduling problem (PFSP) is an important issue in manufacturing. PFSP is the combination of n jobs and m machines of production scheduling problem. Each job must be processed on m machines. All jobs have the same processing procedure but with different processing time. The objective of this paper is to minimize the total completion time of jobs (Minimum Makespan). With the increase number of jobs and machines, the complexity of PFSP increases exponentially. Therefore the optimal solution can not be found in polynomial time. Thus, recent approximation methods have become the popular way to solve PFSP. One such method is the metaheuristic algorithms. In metaheuristic algorithms, hybrid genetic algorithms which combine genetic algorithms and local search methods have been widely studied. The performance of hybrid genetic algorithms is affected by local search methods. Therefore, this study proposed a GA_ENS hybrid genetic algorithm for the PFSP. This algorithm used an extensive neighborhood search method to search the solution space, effectively. For evaluating the performance, test datasets were taken from Taillard''s benchmark. The experimental results of this study were compared against other hybrid genetic algorithms. Comparison results showed that the proposed algorithm outperformed other methods and about 50% of the test instances resulted in known optimal solutions. The proposed algorithm is simple and easy to implement. It can be extended easily to apply to similar combinatorial optimization problems.

碩士
義守大學
工業工程與管理學系
91
Scheduling mainly concerns with allocating resources to tasks over time, under necessary constrains. Appropriate scheduling cannot only reduce manufacturing costs but also reduce possibilities for violating due dates. Finding good schedules for given sets of jobs can thus help factory supervisors effectively control job flows and provide solutions for job sequencing. The flowshop has m machines in which there are n jobs are to be processed through all the machines in the same order. The no-idle flowshop constrain further specifies the machines must process continuously without idle intervals. This manufacturing environment is exists in many industries. The constraint has previously been investigated with linear programming and branch-and-bound algorithm to find the optimal solution with makespan criterion. The no-idle flowshop problem is combinatorial optimization problem and the optimal methods are not efficient in finding solutions. So we should develop some heuristics to yield a good quality solution. In this paper, we use the simulated annealing which proves to obtain the very efficient solutions in the literatures to solve the no-idle flowshop problem. We develop the more suitable algorithm for this problem. In order to evaluate the performance of our simulated annealing algorithm, we compare our algorithm with the structure heuristics and the simulated annealing algorithm proposed in other literature. From the experiment results, we show that the solutions obtained by our simulated annealing outperform other heuristics.

碩士
國立勤益科技大學
工業工程與管理系
97
he paper addressed minimizing total tardiness for the permutation and non-permutation flowshop scheduling problem. The permutation scheduling was applies the decision trees to find out the main attributes and rules which influenced the objective. This study clustered jobs successfully and obtained that the rule of EDD is decidedly influenced the objective under 70% integral accuracy. Furthermore, it generated initial solution via Data Mining and EDD rule. The DML algorithm is proposed via local search technology. The experimental results of DML are better than NEH_T, and also the relatively deviation with AR_TS is approximately 4%. The non-permutation scheduling verified the processing time of two neighbor jobs via Data Mining Technique, and had critical effect with exchanging location. It can easily find the rule which influenced the neighbor location while the whole accuracy is higher than 75%, and then propose the prototypical algorithm of the non-permutation scheduling.

碩士
國立勤益科技大學
工業工程與管理系
99
This study considers two-stage flowshop problem with multiple identical machines at each stage, called two-stage hybrid flowshop. This type of production system is used in printed circuit board manufacture. In order to meet the practice conditions, the machine preventive maintenance based on the job number of completion was taken into account in this study. Biological immune system has a strong recognition, learn, memory ability, and self-adaptation. This study proposes an algorithm based on artificial immune system, called bi-objective immune algorithm (BOIA), to minimize makespan and total tardiness. Two decoding methods corresponding to the two objective functions are used, and recognize antigen, memory and suppression, clone selection, hyper-mutation, receptor editing mechanisms are applied. In order to obtain diversity of antibodies, crowding distance was used to update Pareto archive set. In this study, design of experiment was applied to determine the optimum parameters of BOIA. The Pareto optimal solution was compared with the initial antibody population by applying percentage of improvement and percentage of relative error. The experimental results show that the BOIA can effective evolution, the average percentage of relative error only 5.94%, especially for the improvement of the total tardiness, the average degree of improvement is 71.47%.

碩士
國立高雄第一科技大學
機械與自動化工程所
97
The scheduling is a resource distribution which to satisfy the specific judgement rules under the resource constrain. The most researches focused on a single objective scheduling system in the past. But it is impractical. Therefore the multi-objectives criteria are considered reasonably to solve the scheduling problem. This study aims at the minimization of makespan and maximum tardiness.The genetic algorithm is used to develop a program for solving the flowshop scheduling problem. The program can be gotten the optimal approximate solution in reasonable time based on different jobs and machines combination problems. Finally the result of the study is been approved very efficient for solving multi-objective flowshop scheduling problem.

碩士
朝陽科技大學
工業工程與管理系碩士班
94
The flowshop scheduling problem can be stated as follows. There are n independent jobs and m different machines. There is restriction on the order in which the operations of a job are to be performed. Each machine can process at most one job at a time and each job can be processed on one machine at a time. flowshop scheduling are often encountered in mass production systems. Scheduling problems with no-wait constraints occur in many industries. For instance, in hot metal rolling industries , where the heated metal has to undergo a series of operations at continuously high temperatures before it is cooled in order to prevent defects. Similarly , in the plastic molding and silverware production industries, a series of operations must be performed to immediately follow one another to prevent degradation. We consider the problem of total completion time in a two-machine no-wait flow shop environment. In our research, we present a heuristic solution method for solving large-scaled problems. We also develop a branch and bound algorithm. We use an upper bound based on the heuristic algorithm developed, and propose some dominance rules to help pruning unpromising nodes in the branch-and-bound search tree. Finally, computational experiments are conducted to evaluate the performances of the proposed algorithms. The algorithms can efficiently solve problem with 30 jobs.

碩士
國立成功大學
工業與資訊管理學系碩博士班
100
With the progression of information technology and integrated circuit technology, the demand of wafer has significantly increased, so the wafer manufacturers need an effective dispatching rules in order to reduce production cycle time of the wafers. In order to reflect the rapid increase of the semiconductor production environment, many scholars proposed the multiple orders per job scheduling problem. The multiple orders per job scheduling problem means that the wafer manufacturers receive orders from customers around the world, and in the production process, they assign orders to FOUPs by the orders’ attributes, then dispatch FOUPs by some dispatching rules, finally get the FOUPs’ completion time. But taking into consideration the actual wafer production process, only discuss the multiple order per job scheduling problem can not reflect the real situation, this study consider to include the reentrant flowshop environment to satisfy the real situation. And this study will use Genetic algorithm, NEH algorithm and GA-NEH algorithm to calculate the approximate solution within an acceptable range. Experiment data shows that, in small amount of orders, orders scheduling is more important than FOUPs scheduling on the impact to the FOUP’s completion time. But with amount of orders increasing, the FOUPs scheduling is more important. The result also shows that the performance of GA-NEH algorithm is better than Genetic algorithm and NEH algorithm.

碩士
逢甲大學
統計與精算所
92
This paper addresses a bi-criteria two-machine flowshop scheduling problem when the learning effect is present. The objective is to find a sequence that minimizes a weighted sum of the total completion time and the maximum tardiness. In this article, a branch-and-bound method, incorporating several dominance properties and a lower bound, is presented to search for the exact solution for small job-size problems. In addition, two heuristic algorithms are proposed to overcome the inefficiency of the branch-and-bound algorithm for large job-size problems. Finally, the computational results for this problem are also provided to evaluate the performance of the proposed algorithms.

碩士
國立交通大學
工業工程與管理學系
101
Our study investigates the scheduling problem for the environment of Jumping No-Wait flowshop (JNWF), where jobs are not allowed to wait for machines during the production processes. In the production processes, all jobs are ordered visit a sequence of m machines and some jobs skip some machines in the sequence, which is called "machine jumping". The problem is to determine the sequence of jobs being released for the first machine and our objective is to minimize the makespan. In this paper, we study the characteristics of JNWF scheduling problem and propose a Probability Enhanced Tabu Search (PETS) based on improved Tabu search method. We then compare our heuristic with Radran’s heuristic (1994), on the makespan and the computational time. The numerical studies show that our heuristic performs more effectively and efficiently than Radran’s heuristic on solving the JNWF problems.

碩士
國立雲林科技大學
工業工程與管理研究所碩士班
92
This research studies the two-machine flowshop scheduling problem with limited waiting time constraints. That is jobs must begin processing on a certain machine within a predefined time constraint after completing processing in a prior machine. The objective is to minimize the total weight tardiness. A two-phase scheduling approach is developed to solve this problem. In the first phase, a initial sequence of jobs by simple dynamic dispatching rule is developed. In second phase, preliminary job sequence developed in phase one is divided into subsequence. Each subsequence is considered as a subproblem which is solved by Integer Programming. In static scheduling scenario, when more jobs have tight due date results from the two phase approach are quite near the optimal one. In dynamic scheduling scenario, the two-phase scheduling method is superior to Apparent Tardiness Cost (ATC) rule and Cost Over Time (COVERT) rule in total tardiness and total flow time.

碩士
逢甲大學
統計與精算所
97
This paper investigates a situation in manufacture environment where the job time isn’t a fixed value. That is, the job time becomes long as the waiting time passes, and the scheduling without buffer equipment cause blocking phenomenon. Making the manufacturing time will need more time to complete. Therefore, the job time is assumed as an increasing function of its starting time in this paper. In the manufacture environment, we will schedule these jobs on two-machine flowshop to make the finish time of the last job as shorter as possible, and get to the most availability produce. This paper will take the finished time of the last job as the goal function, and we will develop some dominance properties and lower bounds. Moreover, we also develop a branch-and-bound algorithm to find the optimal solution. Meanwhile, we will propose four heuristic algorithms for a near-optimal solution. Finally, the computational results indicate the branch-and-bound algorithm can handle most instances up to jobs size 32 within a reasonable amount of time, and the weight-combination search algorithm of heuristic algorithms is only with the maximum of the average error percentage of less than 0.70％.

碩士
國立虎尾科技大學
工業工程與管理研究所
97
Many different kinds of scheduling work are widely used both in the manufacturing and service field, the common purpose is how to effectively assign those available sources (machine, equipment, worker, etc.) to maximize the efficiency of related operations and the utilization of those resources. In this research, the focus will be put at the flowshop worker assignment scheduling problem and the purpose is to investigate how to assign the jobs that are waited for processing and those available workers to workstations to minimize the performance measure of makespan. Genetic algorithm is the main tool for solving this specific problem, besides, the result obtained from NEH(Nawaz, Enscore and Ham) method will be used to compare to the result solved by the GA method and demonstrate the superiority of the latter method.

碩士
國立交通大學
工業工程與管理系所
106
In the related high-tech manufacturing industries such as semiconductors. The manufacturing process of products tends to be complicated, and it is often necessary to return to the parallel machine of the workstation in the previous stage for processing. As the number of process programs increases, the capacity of buffer area is limited, and the frequency of reentrant times increases, when the WIPs are obstructed and the scheduling of reentrant hybrid flowshop production processes is not effectively planned, the production cycle will be significantly increased. Although past related research has considered a single stocker in the automatic material handling system to solve WIP storage problems. However, it did not consider the more generalized multiple independent stockers and did not consider the Vehicle Assignment of the transport vehicle. Thus, the problem that the vehicle is assigned to multiple transportation tasks at the same time is neglected, and the problem of assigning the next transportation operation to wait for the completion of the current transportation operation is also ignored. Therefore, this study considers the issue of multiple independent stockers, limited vehicle assignment, and transport time of vehicle for the reentrant hybrid flowshop scheduling problem, with the goal of minimizing the maximum makespan. However, the research has confirmed that the hybrid flowshop scheduling problem is NP-hard. Therefore, this research problem is also NP-hard. Therefore, this study proposes a Cooperative Coevolutionary Hybrid Harmony Search and Genetic Algorithm (CHSGA). Cooperative coevolution has been proven in the past to effectively solve the high-dimensional optimization complexity problem. The concept is to simplify high-dimensional and complex problems into multiple low-dimensional complex sub-problems, and improve the solution diversity of each sub-problem. Although in the past research has combined the cooperative coevolution with the harmony search algorithm. In general, the harmony search algorithm has poor local search ability. Therefore, this study further integrates a genetic algorithm with a better local search ability. Finally, the production environments with different job batch sizes, process stages, and reentrant times, CHSGA can effectively plan production schedules to reduce production cycles than previous algorithms, and effectively allocate empty vehicles handing WIP at the right time.

碩士
國立臺灣科技大學
工業管理系
100
Hybrid scheduling problem has been known widely. However, family scheduling for hybrid flowshop environment has not been studied extensively. This study focused on two-stage hybrid flowshop scheduling problem that exists in footwear industry. The sewing process and the assembly process are two-stage process considered in this study. Sewing process and the assembly process consist of parallel production lines in which one assembly line receives the material from more than one sewing line, which is called as one value stream. A constraint of available lasts exists in second stage. We proposed two methods, Variable Neighborhood Search – Iterated Greedy (VNS-IG) and Genetic Algorithm (GA), to optimize multi-objective functions. The preliminary study was carried out for each method to determine the best parameter setting for computational experiments. We employed EDD rule to compare the performances of proposed methods. Three instances were generated to test the methods for small, medium, and large problem. The result showed that both proposed methods performed much better than EDD rule for our problem. GA becomes the best method since it yielded the lowest deviation of solution for our problem. Moreover, the difference of performance between two algorithms was very significant for large problem. The result also showed that both algorithms need to be improved for large problem since the CPU time increased very significantly.

碩士
大葉大學
工業工程研究所
89
Combinatorial optimization problems are encountered in many areas of science and engineering. Most of the problems are too difficult to be solve optimally, and hence heuristics are used to obtain “good” solutions in reasonable time. In this research, a heuristic which combines two well known local search methods, simulated annealing and tabu search, is presented and applied to solve the n-job and m-machine flow shop sequencing problem with the objective of minimizing makespan. The performance of the proposed heuristic is compared with some other heuristics proposed such as Taillard’s algorithm and BF-TS, the computational experience shown that the efficiency of the presented heuristic is better than that of the others.

碩士
逢甲大學
統計學系統計與精算碩士班
102
This research addresses a two-machine flowshop scheduling problem with a job constraint in which the goal is to find a sequence to minimize the total completion time. To solve the proposed problem, we develop several dominance rules and lower bounds used in a branch-and-bound method for efficiently finding an optimal solution. We also propose a simulated annealing and a largest order value method and their corresponding improvements for a near-optimal solution. In addition, we test the performances of all the proposed algorithms for the small and big numbers of jobs.

碩士
逢甲大學
統計學系統計與精算碩士班
102
The tardiness criterion is one of the most prominent measures in the scheduling area. To keep the tardiness in a lower level means to reduce the penalties incurred for late jobs. On the other hand, the precedence constraint exists in some real-life scheduling problems. For example, in the scheduling of patients from multiple waiting lines or different physicians, patients in the same waiting line for scarce resources such as organs, or with the same physician often need to be treated in the first-come-first serve sequence to avoid ethical or legal issues, and precedence constraints can restrict their treatment sequence. Motivated by these observations, we study a two-machine flowshop scheduling problem to minimize the total tardiness. To solve this problem, we use a genetic and a larger-order-value method for searching a near optimal solution and evaluate the yielded solution compared with an optimal solution obtained by full enumeration method. Finally, we conduct the experiments to test performances of all the proposed algorithms for the small and big numbers of jobs, respectively.

碩士
國立虎尾科技大學
資訊管理研究所
99
In this paper, we consider a time-dependent learning effect into a two-machine flowshop scheduling problem. The time-dependent learning effect of a job is assumed to be a function of total normal processing time of jobs scheduled before it. The classical flowshop scheduling problem with n jobs and m machines, it is well known that except for Johnson’s two-machine makespan case, most of the flowshop scheduling problems are known to be NP-hard, hence, we turn our attention to obtain schedules in which the performance approximates those of optimal schedules. We propose WSPT heuristic algorithms and particle swarm optimization to solve two-machine flowshop scheduling problem with a learning effect, the objective function is the total weighted completion times minimize. The results of three parts, first, the job number form 7 to 9, the use of exhaustive method to obtain the optimal solution to this problem, and WSPT heuristic algorithms and particle swarm algorithm to compare；second, the job number form 10、20、30、50、100, Using the particle swarm Optimization algorithm solving the approximate solution, and heuristic algorithms to compare with WSPT；the second part results show PSO algorithm after several iterations will be convergence after a local optimal solution, therefore, we further proposed PSO algorithm the initial solution into WSPT rules and the SPT rule solution, that prove particle swarm algorithm than WSPT rules and SPT rules good for the learning effect of the flowshop two-machine scheduling problems.

碩士
國立虎尾科技大學
工業工程與管理研究所
97
Scheduling is one of the vital manufacturing practices, thus numerous researchers has involved in this area for the past several decades. Scheduling problems are very complicated, and belong to NP-complete family. Since tremendous effort and time are needed to get the optimal solutions even for a small scale of the problem, studies in this area tends to apply heuristics to efficiently solve for the optimal or near optimal solutions of different kinds of complicated scheduling problems. In this study, a modified NEH (Nawaz, Enscore, and Ham) genetic algorithm (MNGA) has been developed for minimizing the makespan for the flowshop scheduling problems. In order to display the performance of the MNGA, results obtained from the simple genetic algorithm and hybrid NEH genetic algorithm for the same sets of these flow shop scheduling problems are compared to the results solved by the MNGA. Form the comparison, it is clear that the MNGA developed in this study can effectively and efficiently solve for the optimal or near optimal solutions for minimizing the makespan for the flowshop scheduling problems and it is also superior than the simple genetic algorithm and hybrid NEH genetic algorithm.

碩士
國立虎尾科技大學
工業工程與管理研究所
95
The domestic semiconductor industry expands rapidly, batch processing machines are commonly used in burn-in operations. This paper proposes two mixed integer formulation models to schedule batches of jobs on two machines in a flow shop. Then, GA and SA are applied to the batch scheduling problem. A set of jobs with known processing times and sizes has to be grouped, to form batches, in order to be processed on the batch processing machines. Each machine can process a batch as long as the total size of a batch is less than the machine capacity. The processing time of a batch is the longest processing time of all the jobs in that batch. Mixed integer formulation models are proposed when the buffer capacity is unlimited or zero. This research aims at minimizing the makespan for a batch processing machine. Random instances were used to test the effectiveness of the proposed approach. The results obtained from GA were compared with a SA approach and Lingo. The results indicate that the GA was able to arrive at better makespan with shorter run times.

碩士
元智大學
工業工程與管理學系
95
Production scheduling is an NP-hard problem for manufacturing factories. Both the inside capacity conditions and the outside environmental changes can influence the scheduling planning; however, the goods delivery is not allowed to be delayed, which can cause a serious loss of cost and vendor reputation. Therefore, an effective scheduling system for managing unexpected happenings and updating scheduling plans in time is essential to minimize the company’s loss. The theory of constraints and DBR (Drum Buffer Rope) method was used in the research to frame the scheduling managing system, and the machine utilization rate of each bench was used to decide the bottleneck. Authentic data were used to establish CCR buffer and shipping buffer, and the solution of bottleneck resource scheduling was found by ant algorithm. The minimized total tardiness was set as the target value, and greedy method was applied together with pheromone computing to determine the paths by “developing” and “exploring”, and “drum” was obtained. “Rope” was deduced from CCR buffer and drum, and then the shipping plan was generated from shipping buffer and drum to set up a complete input to output scheduling managing system.

碩士
國立屏東科技大學
工業管理系所
96
In recent years, many flowshop scheduling problems are related to no-wait. The so-called no-wait is the operations of a job must be performed in a predetermined order, also they must be performed without any interruption on machines and without any waiting in between machines. That is, each job must be processed continuously from its start to its completion. In traditional scheduling problems, most literature assumes that the processing time of a job is fixed. However, there are many situations where the processing time of a job depends on the starting time or the position of the job in a sequence. In such situations, the actual processing time of a job may be more or less than its normal processing time if it is scheduled later. In order to be more in line with actual production, this research explores the feasibility of applying simulated annealing algorithm to find a solution on a bi-criteria two-machine no-wait flowshop scheduling problem with a learning effect. The objective is to find a sequence to minimize a weighted sum of the maximum complete time and the maximum tardiness. The result shows that employing simulated annealing algorithm can well solve the problem and get better performance.