To see the other types of publications on this topic, follow the link: Flowshop Scheduling.
Dissertations / Theses on the topic 'Flowshop Scheduling'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Flowshop Scheduling.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Park, Malcolm McKenzie. "Flowshop sequencing : a graphical approach /." Connect to thesis, 1990. http://eprints.unimelb.edu.au/archive/00001755.
Full text
2
Moursli, Omar. "Scheduling the hybrid flowshop : branch and bounnd algorithms." Université catholique de Louvain, 1999. http://edoc.bib.ucl.ac.be:81/ETD-db/collection/available/BelnUcetd-11262003-101952/.
Full textAbstract:
This thesis studies Production Scheduling in a multistage hybrid flowshop facility. It first states the general Production Planning and Scheduling problem and highlights some drawbacks of classical solutions. A theoretical decomposition-based approach is introduced whose main issue is to overcome non-efficient capacity utilization. By using Branch and Bound methods, an in-depth analysis of the scheduling part of the system is then carried out throughout the study and development of upper and lower bounds as well as branching schemes. Already-existing and new heuristics are presented and compared on different shop floor configurations. Five different heuristic approaches are studied. By scheduling the HFS one stage at a time the first approach uses different stage sequencing orders. The second and third approaches are mainly list heuristics. The second approach uses ideas derived from the multistage classical flowshop with a single machine per stage, while the third approach uses classical dispatching priority rules. The fourth and fifth approaches, respectively, use random scheduling and local search techniques. Statistical analysis is carried out in order to compare the heuristics and to select the best of them for each shop configuration. Already-existing and new lower bounds on the single stage subproblem are also presented and compared. Three new lower bounds are developed: a dual heuristic based bound, a partially preemptive bound and a heuristic for the so-called subset bound. Some of these lower bounds use a network flow algorithm. A new version of the “Preflow Push” algorithm which runs faster than the original one is presented. The best lower bounds are selected based on numerical tests. Two branch and bound algorithms are presented, an improved version of the sequence enumeration method and a generalization of the so-called interval branching method, along with several bounding strategies. Based on the upper and lower bound studies, several branch and bound algorithms are presented and compared using numerical tests on different shop floor configurations. Eventually, an Object Model for Scheduling Algorithm Implementations (OMSAI), that has been used for the computer implementation of the developed algorithms, is presented.
3
Kaněra, Vojtěch. "Hybridní flowshop se seřízením." Master's thesis, Vysoká škola ekonomická v Praze, 2008. http://www.nusl.cz/ntk/nusl-5109.
Full textAbstract:
This work should serve as a source of information on the issue of production scheduling. The work is particularly focused on the relatively new terms in optimization of processing of production batches area, such as flowshop and its modifications in the form of so-called hybrid flowshop. The work is divided into five chapters. The first chapter consists of an introduction. In the second chapter I mention the theory of scheduling, the third part deals with the history of flowshop and in the fourth part I check the functionality of new models on real data. In conclusion I summarize the contents of work, comment resulting calculations and deliver the practical usage of flowshop.
4
Yamada, Takeshi. "Studies on Metaheuristics for Jobshop and Flowshop Scheduling Problems." 京都大学 (Kyoto University), 2003. http://hdl.handle.net/2433/148279.
Full text
5
Luo, Hao, and 罗浩. "Hybrid flowshop scheduling with job interdependences using evolutionary computing approaches." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2012. http://hub.hku.hk/bib/B47849551.
Full textAbstract:
This research deals with production scheduling of manufacturing systems that predominantly consist of hybrid flowshops. Hybrid Flowshop Scheduling (HFS) problems are common in metal working industries. Their solution has significant inferences on company performance in a globally competitive market in terms of production cycle time, delivery dates, warehouse and work-in-process inventory management. HFS problems have attracted considerable research efforts on examining their scientific complexity and practical solution algorithms. In conventional HFS systems, an individual job goes through the flowshop with its own processing route, which has no influence on other jobs. However, in many metal working HFS systems, jobs have interdependent relationships during the process. This thesis focuses on addressing two classes of HFS problems with job interdependence that have been motivated by real-life industrial problems observed from our collaborating companies.
The first class of HFS problems with job interdependence are faced by manufacturers of typically standard metal components where jobs are organized in families according to their machine settings and tools. Family setup times arise when a machine shifts from processing one job family to another. This problem is compounded by the challenges that the formation of job families is different in different stages and only a limited number of jobs can be processed within one setup. This class of problems is defined as HFS with family setup and inconsistent family formation.
The second class of HFS problems with job interdependence is typically faced in a production process consisting of divergent operations where a single input item is converted into multiple output items. Two important challenges have been investigated. One is that one product can be produced following different process routes. The other is that the total inventory capacity is very limited in the company in the sense that the inventory spaces are commonly shared by raw materials, work-in-process items and finished products. This class of problems is defined as HFS with divergent production and common inventory.
The aim is to analyze the general characteristics of HFS with job interdependence and develop effective and practical methodologies that can tackle real-world constraints and reduce the scheduling effort in daily production.
This research has made the following contributions: (1) A V-A-X structural classification has been proposed to represent the divergent (V), convergent (A) and mixed (X) job interdependent relations during the production. (2) A genetic algorithm based approach and a particle swarm optimization based approach have been developed to solve two classes of HFS problems with job interdependence, respectively. The computational results based on actual production data have shown that the proposed solutions are robust, efficient and advantageous for solving the practical problems. (3) A waiting factor approach and delay timetable approach have been developed to extend the solutions space of two classes of HFS problems by inserting intentional idle times into original schedules. The computational results have indicated that better schedules can be obtained in the extended solution spaces.published_or_final_version
Industrial and Manufacturing Systems Engineering
Doctoral
Doctor of Philosophy
6
Ibrahem, Al-mehdi Mohamed M. "Scheduling optimization of cellular flowshop with sequence dependent setup times." Proceedings of the 47th CIRP Conference on Manufacturing Systems, 2014. http://hdl.handle.net/1993/30730.
Full textAbstract:
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
7
Dai, Jianbin. "Batch scheduling of two-machine limited-buffer flowshop with setup and removal times." Diss., Available online, Georgia Institute of Technology, 2004:, 2003. http://etd.gatech.edu/theses/available/etd-04062004-164623/unrestricted/dai%5Fjianbin%5F200312%5Fphd.pdf.
Full text
8
Shieh, Alireza. "A simulated annealing approach for flexible flowshop scheduling to maximize flexibility." Morgantown, W. Va. : [West Virginia University Libraries], 2004. https://etd.wvu.edu/etd/controller.jsp?moduleName=documentdata&jsp%5FetdId=18.
Full textAbstract:
Thesis (M.S.)--West Virginia University, 2004.Title from document title page. Document formatted into pages; contains xii, 112 p. : ill. Includes abstract. Includes bibliographical references (p. 95-99).
9
Liu, Weibo. "Scheduling algorithm development for permutation flowshop under static and dynamic environment." Thesis, Queen's University Belfast, 2017. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.727425.
Full textAbstract:
Permutation flowshop scheduling problem (PFSP) is a classical combinatorial optimisation problem, which has attracted much attention from academia and industry in the last two decades. However, there are still great challenges to overcome. In existing heuristic methods, jobs with similar processing times cannot be efficiently distinguished, so that jobs are not effectively sequenced, which could result in a poor scheduling solution. Also, most existing research has focused on static PFSPs with a single-objective, however, a single objective is sometimes not good enough, and multiple objectives are often required. In addition, many interruptions or disturbances such as newly arrived orders frequently occur, which creates significant challenges and needs to be addressed in scheduling research. This work focused on new job differentiation methods, multi-objective optimisation, and dynamic scheduling methods in static and dynamic environments respectively. In the static environment, three new priority rules using high moments of a probability distribution of job processing times are proposed, for the first time, so that jobs can be effectively distinguished and ordered. As a result, three new heuristics as well as a new tie-breaking rule are developed based on Nawaz-Enscore-Ham (NEH) heuristic for single-objective PFSPs. For multi-objective PFSPs, with makespan and idletime as the bicriteria, a new heuristic method is developed by incorporating a new priority rule and a new tie-breaking rule. As a result, our work has proved that makespan and idletime are not equivlent in sheduling optimisation, which corrects the existent misunderstanding in the scheduling community. In the dynamic environment, PFSPs with new order arrivals are investigated, and a new heuristic method is proposed by integrating a new match-up and real-time strategy through orders’ mixing. Also, a new meta-heuristic algorithm derived from iterated greedy algorithm is developed with a new enhanced destruction & construction method and a novel repair mechanism. For ease of application, a digital tool is developed to automatically implement these algorithms. A real industrial case is used to demonstrate the validity of these scheduling methods.
10
Luo, Hao. "Two-stage hyhrid flowshop scheduling in a metalworking company using genetic algorithm." Click to view the E-thesis via HKUTO, 2009. http://sunzi.lib.hku.hk/hkuto/record/B41758109.
Full text
11
Luo, Hao, and 羅浩. "Two-stage hyhrid flowshop scheduling in a metalworking company using genetic algorithm." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2009. http://hub.hku.hk/bib/B41758109.
Full text
12
Cheng, Wei. "Heuristics for two-machine flowshop scheduling with setup times and an availability constraint /." Electronic version (PDF), 2007. http://dl.uncw.edu/etd/2007-3/chengw/weicheng.pdf.
Full text
13
Almasarwah, Najat E. "Family Formation, Loading and Batch-Cyclic Flowshop Scheduling in Cellular Manufacturing Systems." Ohio University / OhioLINK, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1503605158270554.
Full text
14
Mainieri, Guilherme Barroso. "Heurísticas para a minimização do atraso total no ambiente flowshop com múltiplos processadores." Universidade de São Paulo, 2009. http://www.teses.usp.br/teses/disponiveis/3/3136/tde-13072009-172614/.
Full textAbstract:
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.
15
Palekar, Nipun Pushpasheel. "Job Sequencing & WIP level determination in a cyclic CONWIP Flowshop with Blocking." Thesis, Virginia Tech, 2000. http://hdl.handle.net/10919/34997.
Full textAbstract:
A CONWIP (Constant Work-In-Progress) system is basically a hybrid system with a PUSH-PULL interface at the first machine in the line. This research addresses the most general case of a cyclic CONWIP system by incorporating two additional constraints over earlier studies namely; stochastic processing times and limited intermediate storage. One of the main issues in the design of a CONWIP system is the WIP level 'M', to be maintained. This research proposes an iterative procedure to determine this optimal level. The second main issue is the optimization of the line by determining an appropriate job sequence. This research assumes a 'permutational' scheduling policy and proposes an iterative approach to find the best sequence. The approach utilizes a controlled enumerative approach called the Fast Insertion Heuristic (FIH) coupled with a method to appraise the quality of every enumeration at each iteration. This is done by using a modified version of the Floyd's algorithm, to determine the cycle time (or Flow time) of a partial/full solution.
The performance measures considered are the Flow time and the Interdeparture time (inverse of throughput). Finally, both the methods suggested for the two subproblems, are tested through computer implementations to reveal their proficiency.Master of Science
16
Filho, Marcio Antonio Ferreira Belo. "Programação de produção e dimensionamento de lotes para flowshop." Universidade de São Paulo, 2010. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-17112010-101418/.
Full textAbstract:
O problema integrado de programação de produção e dimensionamento de lotes em ambiente fowshop consiste em estabelecer tamanhos de lotes de produção e alocar máquinas para processá-los dentro de um horizonte de planejamento, em uma linha de produção com máquinas dispostas em série. O problema considera que a demanda deve ser atendida sem atrasos, que a capacidade das máquinas deve ser respeitada e que as preparações de máquinas são dependentes da sequência de produção e preservadas entre períodos do horizonte de planejamento. O objetivo é determinar uma programação de produção visando minimizar os custos de preparação de máquina, de produção e de estoque. Um modelo matemático da literatura é apresentado assim como procedimentos para obtenção de limitantes inferiores. Além disso, abordamos o problema por meio de distintas versões da metaheurística Times Assíncronos (A-Teams). Os procedimentos propostos foram comparados com heurísticas da literatura baseadas em Programação Inteira Mista (MIP). As metodologias desenvolvidas e os resultados obtidos são apresentados nesta dissertaçãoThe integrated production scheduling and lot sizing problem in a fowshop environment consists in establishing production lot sizes and alocate machines to process them inside a planning horizon, in a production line with machines arranged in series. The problem considers that demand must be met without backlogging, the capacity of the machines must be respected, machine setup are sequence-dependent and preserved between periods of the planning horizon. The objective is to determine a production schedule to minimize the setup, production and inventory costs. A mathematical model from the literature is presented as well as procedures for obtaining lower bounds. In addition, we propose to address the problem through different versions of the metaheuristic Asynchronous Teams (A-Teams). The procedures were compared with literature heuristics based on Mixed Integer Programming (MIP). The developed methodologies and the obtained results are presented in this dissertation
17
Gomes, Francisco Regis Abreu. "Algoritimo genÃtico aplicado aos problema de seqÃenciamento permutacional flowshop sem e com restriÃÃo de espera." Universidade Federal do CearÃ, 2008. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=1220.
Full textAbstract:
CoordenaÃÃo de AperfeiÃoamento de NÃvel SuperiorNeste 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
18
Branco, Fábio José Ceron. "Avaliação de métodos heurísticos para o problema no-wait flowshop com o critério de minimização da duração total da programação." Universidade de São Paulo, 2006. http://www.teses.usp.br/teses/disponiveis/18/18140/tde-07122006-100703/.
Full textAbstract:
Este trabalho apresenta o problema de programação de operações em máquinas no ambiente no-wait flowshop com o critério de minimização da duração total da programação. Aplicações para o problema no-wait flowshop podem ser encontrados em muitas indústrias, por exemplo, em indústrias de processamento de metais, químicos e farmacêuticos. Neste trabalho, são propostos e avaliados novos métodos heurísticos para o problema, e a superioridade do melhor método proposto é comprovada através uma extensa experimentação computacional.This work deals with the no-wait flowshop scheduling problem with the objective of minimizing total completion time. Applications of no-wait flowshop can be found in many industries, for example, in steel factories, chemical and pharmaceutical. In this work, we propose evaluate new heuristics methods for the problem. Experimental results show that the best proposed heuristic provides better solutions concerning both the solution quality and computational effort.
19
Urlings, Thijs. "Heuristics and metaheuristics for heavily constrained hybrid flowshop problems." Doctoral thesis, Universitat Politècnica de València, 2010. http://hdl.handle.net/10251/8439.
Full textAbstract:
Due to the current trends in business as the necessity to have a large catalogue of products, orders that increase in frequency but not in size, globalisation and a market that is increasingly competitive, the production sector faces an ever harder economical environment. All this raises the need for production scheduling with maximum efficiency and effectiveness.
The first scientific publications on production scheduling appeared more than half a century ago. However, many authors have recognised a gap between the literature and the industrial problems. Most of the research concentrates on optimisation problems that are actually a very simplified version of reality. This allows for the use of sophisticated approaches and guarantees in many cases that optimal solutions are obtained. Yet, the exclusion of real-world restrictions harms the applicability of those methods. What the industry needs are systems for optimised production scheduling that adjust exactly to the conditions in the production plant and that generates good solutions in very little time. This is exactly the objective in this thesis, that is, to treat more realistic scheduling problems and to help closing the gap between the literature and practice.
The considered scheduling problem is called the hybrid flowshop problem, which consists in a set of jobs that flow through a number of production stages. At each of the stages, one of the machines that belong to the stage is visited. A series of restriction is considered that include the possibility to skip stages, non-eligible machines, precedence constraints, positive and negative time lags and sequence dependent setup times. In the literature, such a large number of restrictions has not been considered simultaneously before. Briefly, in this thesis a very realistic production scheduling problem is studied.
Various optimisation methods are presented for the described scheduling problem. A mixed integer programming model is proposed, in order to obtaiUrlings ., T. (2010). Heuristics and metaheuristics for heavily constrained hybrid flowshop problems [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/8439
Palancia
20
Bellanger, Adrien. "Ordonnancement sur les machines à traitement par batches et contraintes de compatibilité." Phd thesis, Institut National Polytechnique de Lorraine - INPL, 2009. http://tel.archives-ouvertes.fr/tel-00606383.
Full textAbstract:
Dans cette thèse, nous avons traité les problèmes d'ordonnancement d'ateliers de type flow- shop hybride à deux étages avec machines à traitement par batches sur le second étage et compatibilité entre les tâches. Les durées opératoires des tâches sont données par des intervalles, et les tâches sont dites compatibles si elles partagent une même durée d'exécution. Pour le problème de minimisation de la date de fin d'ordonnancement de ce type d'atelier, nous avons développé 6 heuristiques à performances garanties. D'après les expériences réalisées, ces heuristiques sont efficaces sur de grandes instances. Pour les petites instances, nous avons présenté deux méthodes exactes de type procédures par séparation évaluation qui permettent de résoudre des instances de 20 tâches. Nous avons également développé un schéma d'approximation polynomial (PTAS) utilisable lorsque les durées d'exécution sur le premier étage sont identiques. En complément de ces travaux, nous avons également étudié d'autres problèmes de minimisation de critères réguliers sur une machine à traitement par batches. Nous avons développé des algorithmes de programmation dynamiques pseudo-polynomiaux pour les problèmes de minimisation de la somme des dates de fin d'exécution et pour les problèmes avec dates de fin souhaitées. Afin de compléter ces résultats de complexité, nous avons montré la NP-complétude des problèmes avec dates de fin souhaitées.
21
Liou, Jiam-Jie, and 劉建杰. "MILP Models for Flowshop Scheduling Problems." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/4hq7yc.
Full textAbstract:
碩士國立臺北科技大學
工業工程與管理研究所
98
Permutation Flowshop Scheduling Problem (PFSP) is an important issue in manufacturing. To improve the system performance, the decision makers need to reduce process time and inventory level, enhance ratio of utilization, and delivery on time. The problem of an n-job, m-machine Flowshop Scheduling Problem is discussed. A mixed-integer linear program (MILP) is formulated with considerably reduced number of integer binary variables. Most of research in production scheduling is concerned with the minimization of a single criterion. However, scheduling problems often involve more than one aspect and therefore require multicriteria analysis. In this study, a multicriteria an n-job, m-machine flowshop scheduling problem is considered. The objective function of the problem is minimization of the makespan, total complete time, total tardiness time, maximum tardiness time, total machine idle time, and total job wait time. This research first creates a mathematical MILP model of MPFSP, and then computes this model by LINGO. To validate the effectiveness of the proposed model, this research uses the earlier studies as benchmarks to compare with the result of this study. In the comparison result, it is appeared that the effectiveness of the proposed model is well, and it can be used as valuable reference for practitioners to improve their operational efficiency within a reasonable amount of computational effort.
22
ZHENG, JIA-WEN, and 鄭佳汶. "Mixed-blocking Permutation Flowshop Scheduling Problems." Thesis, 2019. http://ndltd.ncl.edu.tw/handle/x69ved.
Full textAbstract:
碩士國立臺北科技大學
工業工程與管理系
107
In the flowshop environment, different constraints between successive machines may cause various types of blocking. The mixed-blocking permutation flowshop is a flowshop with various types of blocking constraints at the same time. This study proposes a simulated annealing (SA) algorithm to minimize the total flow time for the mixed-blocking permutation flowshop scheduling problem (MBPFSP). To evaluate the efficiency of the proposed algorithm, we compared it with two iterated greedy (IG)-based algorithms and a state-of-the-art constraint guided local search (CGLS) algorithm (Riahi et al., 2019) using the same benchmark instances and termination criterion. The experimental results show that the proposed SA algorithm outperforms over compared methods.
23
朱馨吟. "No-wait Flowshop Scheduling with Parallel Machines." Thesis, 2008. http://ndltd.ncl.edu.tw/handle/22767750508928650121.
Full textAbstract:
碩士國立交通大學
工業工程與管理系所
96
This study addresses a no-wait flowshop scheduling problem with parallel machines at the starting stage. We proposed two effective methods, called TS_T and TS_P, to determine the jobs sequence, which is a priority list of the processing order for the jobs in the final schedule. Several examples are designed to show that the proposed heuristics are accurate and outperform the existing methods used to solve a no-wait flowshop problem and a parallel machines scheduling problem. Furthermore, based on the scheduling results produced by the proposed heuristics, the marginal benefits of parallel machines have been analyzed and are believed to support decision-making of the number of the appropriate number of parallel machines in starting stage.
24
Chen, Chun-Han, and 陳軍翰. "Flowshop manufacturing cell scheduling problems with rejection." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/8x466u.
Full textAbstract:
碩士國立臺北科技大學
工業工程與管理系碩士班
100
The Flowshop manufacturing cell scheduling problem (FMCSP) with sequence-dependent family setup times (SDFSTs) has become a key area in the field of scheduling. We want to discuss the FMCSPs with rejection because the company capacity is limited in the real word. We can not satisfy every customer. Therefore, we need to know how to choose the right orders, because if we can not finish the product before the customer’s deadline, the product will lose its value. Moreover, the customers will lose their confidence toward us. In this study, a harmony search algorithm was presented for this problem is to maximize total revenue. To validate the performance of the proposed approach, we use Harmony Search, Revised Harmony Search, Brute-Force Search to deal with small problem. On the other hand, to deal the big problem, we use HS and RHS to compare their efficiency. The computational results showed that the RHS significantly outperforms the original HS in big problems. It is believed that it can serve as a new benchmark approach for future research.
25
Wu, Chien-Hua, and 吳建樺. "Distributed Flowshop Scheduling Problems with Blocking Constrain." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/qarnvg.
Full textAbstract:
碩士國立臺北科技大學
工業工程與管理系碩士班
101
Among the ordinary flow shop, there are many temporary storage area, place the workpiece is waiting, but many of these do not exist in practice environments temporary area. Therefore derive blocking flowshop scheduling problem. Flowshop scheduling research has been focused, with the recent changes in the processing environment, from a single factory slowly transformed into the trend of many factories, therefore, this study assigned for the process factory to join the factors and blocking constrain. The optimization criterion is the minimization of the maximum completion time, and use the harmony search algorithm (HS) as a solution based on adding NEH1 algorithm concepr to slove it. The computational result show that the study proposes a modified harmony search algorithm very excellent performance of the proposed.
26
Bai, Ching-Hsu, and 白景旭. "Distributed Multi-stage Flexible Flowshop Scheduling Problems." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/958nps.
Full textAbstract:
碩士國立臺北科技大學
工業工程與管理系碩士班
101
In todays globalized environment, Producing products in different locations is a global trend, therefore the DFSP is increasing attention. In practice, MSHF problem is more impotant then before, The purpose of this study is to solve distributed multi-stage flexible flowshop scheduling problems with Iterated greedy heuristic.In view of the the strongly NP-hard nature of this problem, Iterated greedy heuristic has better experimental results then other heuristics. In this paper, we compared the revised IG with basic ICA for the DMFSP with makespan criterion. As our experimental results, the revised IG is better than the basic ICA.
27
Peng, Ting-Chia, and 彭亭嘉. "Distributed Flowshop Scheduling Problems with Predictive Maintenance." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/2m4f32.
Full textAbstract:
碩士國立臺北科技大學
工業工程與管理系碩士班
101
With the increase of multinational, with high quality, low cost and low risk of multi-plant production model has been adopted by many companies, thereby enabling the distributed flowshop scheduling problems (DFSP) have gradually been more research attention of scholars. Availability of machine based production scheduling important factor, however, the majority of DFSP literature ignores machine availability and assumes that machine is available all the time. In reality, machines physically deteriorate with increased usage and time. Thus, there is an intense need for companies to reduce unexpected breakdowns and remain competitive, and maintenance strategy should be integrated into production scheduling. In this study, using of Genetic Algorithm (GA) to solve the makespan minimization with predictive maintenance for distributed flowshop scheduling problems (DFSPPM), and construct a mixed integer programming model (MILP). Related research may provide practical industry applications, and as further to relevant academic research references.
28
Yang, Dar-Li, and 楊達立. "Some Generalized Two-Machine Flowshop Scheduling Problem." Thesis, 1994. http://ndltd.ncl.edu.tw/handle/66011464809492698777.
Full textAbstract:
博士國立清華大學
工業工程研究所
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.
29
Lin, Zhi-Yu, and 林志諭. "Genetic algorithm for multi-objective flowshop scheduling problem." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/15601955448224589260.
Full textAbstract:
碩士國立勤益科技大學
工業工程與管理系
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.
30
He, Cheng-Ding, and 何承鼎. "Distributed Flowshop Scheduling Problems with No-idle Constraint." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/cxnmn3.
Full textAbstract:
碩士國立臺北科技大學
工業工程與管理系碩士班
103
In the no-idle flowshop scheduling problem, machines cannot be idled after finishing one job and before starting the next one. In practical, machines show this behavior as it might be technically unfeasible or uneconomical to stop a machine between jobs. For instance, productions of integrated circuit via photolithography, steel making and fiberglass processing, among others. Flowshop scheduling research has been focused with the recent changes in the processing environment, from a single factory slowly transformed into the trend of many factories. Therefore, this study assigned for the process factory to join the factors and no-idle constraint. The optimization criterion is the minimization of the maximum completion time (makespan). And we propose the IRG algorithm to solve it. The results show that the proposed IRG algorithm is superior to the IGPR algorithm by a significant margin.
31
"Scheduling the hybrid flowshop : branch and bounnd algorithms." Université catholique de Louvain, 1999. http://edoc.bib.ucl.ac.be:81/ETD-db/collection/available/BelnUcetd-11262003-101952/.
Full text
32
Yang, Ching-I., and 楊清一. "Hybrid Particle Swarm Optimizations for Flowshop Scheduling Problems." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/35126852320955355102.
Full textAbstract:
博士國立高雄第一科技大學
工程科技研究所
101
Traditional particle swarm optimization (PSO) has the tendency to be trapped at local optimal solution or premature convergence and cannot improve the solutions by fine-tuning. In this dissertation, we utilize the concept of PSO with non-linear time varying evolution (PSO-NTVE) to approach the optimal solutions for flowshop scheduling problems (FSPs). Two hybrid PSO approaches for FSPs are developed. First, hybrid Taguchi-based PSO (HTPSO) is proposed with three features which are different from the existing methods: (I) enhancement of search capability by the use of dynamic weights selected by fuzzy inference system (FIS) instead of dynamic weights selected randomly (II) performing a systematic reasoning way of Taguchi-based crossover operation that avoids the scheduling conflicting problem to find an optimal solution instead of performing crossover operation based on a random process. The two major tools in the systematic reasoning way of Taguchi-based crossover operation are (1) the signal-to-noise ratio (SNR) used to measure quality and (2) the orthogonal arrays (OAs) used for simultaneously studying multiple parameters; (III) an easy way to generate the Pareto optimum solutions found so far so that the best offspring (solutions) can be retained. A numerical example is given to demonstrate the application of the proposed HTPSO and its good performance. The numerical results show that the HTPSO effectively enhances particle swarm optimization. The improvement achieved by the HTPSO also exceeds that obtained by existing methods for finding Pareto optimum solutions for FSPs. Therefore, the proposed HTPSO method effectively solves multi-objective FSPs. Next, in order to improve the searching performance, a hybrid sliding level Taguchi-based PSO (HSLTPSO) algorithm for FSP is proposed with two features: (I) A new systematic reasoning way with considering the influence of tuning factors α, β and γ in Taguchi-based crossover without the conflicting problem of non-feasible solutions is presented in this study to find the better particles. (II) an easy way to generate the Pareto optimum solutions found so far so that the best offspring (solutions) can be retained. As a result, it exhibits a significant improvement in Pareto optimal solutions of FSP. Meanwhile, a numerical example is used to illustrate the application of the proposed HSLTPSO and its performance. The study results show that the hybrid method can enhance the particle swarm optimization. Therefore, HSLTPSO is an effective means in solving a multi-objective flowshop scheduling problem. In conclusion, because of the combined use of Taguchi-based crossover operation and PSO, the proposed HTPSO and HSLTPSO are robust and achieve quick convergence. Therefore, we have found that HTPSO and HSLTPSO approaches which use the proposed features are the most suitable PSO algorithms for solving the flowshop scheduling problems. Simulation results have shown that the proposed HTPSO and HSLTPSO algorithms are the useful methods for solving the existing cases and outperform the existing methods of test problems. In this study, we know that the HSLTPSO algorithm is superior to the HTPSO algorithm and HTGA algorithm.
33
Liu, Jian-Kuan, and 劉鑑寬. "Scheduling for M-Machine Jumping No-Wait Flowshop." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/24691995275188223976.
Full textAbstract:
碩士國立交通大學
工業工程與管理學系
98
This study investigates the scheduling of jumping no-wait flowshop(JNWF) problems. These problems have a constraint that jobs can not wait for machine during production process; the sequencing of jobs by the machine is similar, but due to the difference of jobs' types, jobs may skip some process of machines. This research is based on the specific of JNWF sequencing problems, with the minimum makespan as the target. By deriving 2 new algorithms (FBS and FBS2) from tabu search, we determine the priority of the jobs from the machine. 4 methods (FBS, FBS2, Li’s TS2 and Tsai’s ITS) are compared in terms of initial solution, final solution and computed time. It is found that FBS and FBS2 are significantly better than TS2 and ITS in terms of initial and final solution, but there is not much difference between these 4 methods in terms of computed time and during scenario when lesser machines are used.
34
Hung, Chun Hung, and 洪正鴻. "Mathematical and Heuristic Modelling in Flowshop Scheduling with Unrelated." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/12977708623132183220.
Full textAbstract:
碩士大葉大學
工業工程學系碩士班
91
In this research, a non-identical parallel machine flow shop scheduling problem of minimizing mean flow time is considered. In the past few years, in order to simplify the scheduling problem, most of research assumes setup and removal times are even negligible or part of the processing time. In this research, we look the setup, processing, and removal times as separatable, then take the sequence-independent setup and dependent removal times into account. To solve the addressed problem two different solving models are developed. First, a 0-1 integer programming model is constructed; however, the mathematical model is too time consuming to solve the medium or large size problem, thus, a simulated annealing based heuristic is proposed to get an near optimal schedule in a reasonable computation time. During the research, the parameters used in the heuristics that affect the solution quality and efficiency are analyzed and designed; then for the constructed heuristic, a good parameter setting is suggested. The experimental results are reported, and provided for the references for the further research.
35
Chou, Fuh-Der, and 周富得. "A Study On The Flowshop Scheduling With Bicriteria Problems." Thesis, 1997. http://ndltd.ncl.edu.tw/handle/41530117303742946208.
Full textAbstract:
博士國立交通大學
工業工程與管理學系
85
To increase a flowshop performance, to lower both throughput time and work inprocess (WIP) as much as possible is necessary. In general, the scheduling criterion on makespan minimization can effectively shorten the throughput time while the scheduling criterion on total flow time minimization can effectively reduce the WIP. This study attempts to minimize the weighted sum of the abovetwo scheduling criteria in a flowshop environment. Three sub-problems : (1)static scheduling with bicriteria problem in a two-machine flowshop, (2)dynamic scheduling with bicriteria problem in a two-machine flowshop, (3)dynamic scheduling with bicriteria problem in a multi-machine flowshop are tackled in this study. A frozen-event procedure is proposed to transformdynamic scheduling problems into static ones. For each sub- problem, the corresponding heuristic scheduling algorithm is developed. Integer programmingmodels are formulated to validate the performance of those heuristic schedulingalgorithms. Results demonstrate that the proposed algorithms can efficiently solve the flowshop scheduling with bicriteria problems.
36
Hsiu-Hsiu, Weng, and 翁秀繡. "Genetic Algorithm for Two-stage Hybrid Flowshop scheduling problem." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/34156437397140462245.
Full textAbstract:
碩士國立勤益科技大學
工業工程與管理系
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.
37
林耿漢. "A Tabu Search Approach to Scheduling Flowshop Manufacturing Cell." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/74235747110432827885.
Full textAbstract:
碩士國立交通大學
工業工程與管理學系
99
The tabu-search mechanism, a type of meta-heuristic algorithms, has been widely used in solving complex space-search problems. Most prior research focused on how to apply or enhance the tabu-search mechanism to various problems. Aside from the traditional track, this research examines a new research issue—Can the adoption of a new solution representation scheme improve the performance of the tabu-search mechanism? A scheduling problem called flowshop manufacturing cell with permutation is used as the problem context, and two tabu-search algorithms are compared. The two algorithms, essentially the same in algorithmic flow, are distinct in using two different solution representation schemes (respectively called Sold and Snew). Noticeably, Sold was developed by prior studies and Snew is by Wu et al. (2011); the two algorithms are named Tabu-Sold and Tabu-Snew accordingly. Extensive numerical experiments reveal that Tabu-Snew comprehensively outperforms Tabu-Sold. This finding highlights an important new research track—exploring new solution representation schemes while applying meta-heuristic algorithms to various space-search problems.
38
潘冠銘. "A Memetic Algorithm Approach to Scheduling Flowshop Manufacturing Cell." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/33545871708780086907.
Full textAbstract:
碩士國立交通大學
工業工程與管理學系
99
The memetic algorithm, a type of meta-heuristic algorithms, has been widely used in solving complex space-search problems. Most prior research focused on how to apply or enhance the search mechanism to various problems. Aside from the traditional track, this research examines a new research issue—Can the adoption of a new solution representation scheme improve the performance of the memetic algorithm? A flowshop manufacturing cell scheduling problem with permutation is used as the problem context, and two memetic algorithms are compared. The two algorithms, essentially the same in algorithmic flow, are distinct in using two different solution representation schemes (respectively called Sold and Snew). Noticeably, Sold was developed by prior studies and Snew is by Wu et al. (2011); the two algorithms are named Memetic-Sold and Memetic-Snew accordingly. Extensive numerical experiments reveal that Memetic-Snew mostly outperforms Memetic-Sold. This finding highlights an important new research track—exploring new solution representation schemes while applying meta-heuristic algorithms to various space-search problems.
39
曾偉杰. "A Simulated Annealing Approach To Scheduling Flowshop Manufacturing Cell." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/22184302475067095864.
Full textAbstract:
碩士國立交通大學
工業工程與管理學系
99
Simulated Annealing (SA), a type of meta-heuristic algorithms, has been widely used in solving complex space-search problems. Most prior research focused on how to apply or enhance SA to various problems. Aside from the traditional track, this research examines a new research issue—Can the adoption of a new solution representation scheme improve the performance of SA? A scheduling problem called Flowshop Manufacturing Cell is used as the problem context, and two SAs are compared. The two algorithms, essentially the same in algorithmic flow, are distinct in using two different solution representation schemes (respectively called Sold and Snew). Noticeably, Sold was developed by prior studies and Snew is by Wu et al. (2011); the two algorithms are named SA-Sold and SA-Snew accordingly. Extensive numerical experiments reveal that the two algorithms performs equally well in small and medium setup time (SSU/MSU) scenarios. Yet, SA-Snew outperforms SA-Sold at large setup time (LSU) scenarios. This finding highlights an important new research track—exploring new solution representation schemes while applying meta-heuristic algorithms to various space-search problems.
40
Hao-tun, Teng, and 鄧浩敦. "A Hybrid Genetic Algorithm for the Flowshop Scheduling Problem." Thesis, 2000. http://ndltd.ncl.edu.tw/handle/46941160360681385525.
Full textAbstract:
碩士逢甲大學
工業工程學系
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.
41
Lin, Ya-Tai, and 林亞泰. "A Genetic Local Search Algorithm for Flowshop Scheduling Problems." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/26168249249337274725.
Full textAbstract:
博士國立中興大學
資訊科學與工程學系
97
The flowshop scheduling problem (FSSP) is a very well-known scheduling problem. Over the past years, the researches on FSSP were aiming at the criterion of makespan minimization. Recently, the FSSP to total flowtime minimization has drawn more researchers’ attention. Besides, researches on no-wait flowshop scheduling problem reflecting to many industries like steel production, food processing, and chemical industry have been increased. In this dissertation, a genetic local search algorithm is proposed to solve the FSSP with both makespan and total flowtime criterion, and also the no-wait FSSP with makespan criterion. The proposed algorithm hybridizes the genetic algorithm and a novel local search scheme that combines two local search methods: the Insertion Search (IS) and the Insertion Search with Cut-and-Repair (ISCR). It employs the genetic algorithm to do the global search, and two local search methods to do the local search. Two local search methods play different roles in the search process. The IS is for searching a small neighborhood while the ISCR is for searching a large neighborhood. Furthermore, the orthogonal-array-based crossover operator is designed to enhance the genetic algorithm(GA)’s capability of intensification. The experiment results show a great advantage of combining two local search methods. The performance of the proposed genetic local search algorithm is very competitive. For the FSSP with the total flowtime criterion, it improved 66 solutions out of the 90 current best solutions reported in the literature for short-term search, and it also improved all the 20 current best solutions reported in the literature for long-term search. For the FSSP with the makespan criterion, the proposed algorithm also outperforms the other three methods recently reported in the literature. When applying the proposed genetic local search algorithm to the no-wait FSSP with makespan criterion, in short-term search, the proposed algorithm found the optimal solutions for all eight Carlier’s benchmark problems. Also, for Reeves’ benchmark problems, the proposed algorithm improved five out of the twenty-one current best solutions reported in the literature and achieved the current best solutions for fourteen of the remaining sixteen problems.
42
Lin, Yin-Shan, and 林吟珊. "Distributed Flowshop Scheduling Problems with Sequence-Dependent Setup Times." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/d4rjwz.
Full textAbstract:
碩士國立臺北科技大學
工業工程與管理系碩士班
101
Since many industries from a single factory into a multi-mode of production, distribution flowshop scheduling problem scheduling research in recent years become one of the important directions. In face scheduling performance is good or bad is often affected by the setup times. In the past that distribution flowshop scheduling problems studies have ignored the sequence dependent setup time. This research provided two kinds of Iterated Greedy Algorithm (IG) to solve the problem, and verify the solution of efficiency from the proposed Revised Iterated Greedy Algorithm (RIG). The experimental results are compared, which shows that Revised Iterative Greedy Algorithm can obtain the better solution performance in the distributed flowshop scheduling problem with setup times. And it provides practical application of industry and use as a reference for subsequent academic research.
43
Lu, Hsiao-Shan, and 盧筱姍. "Distributed Flowshop Scheduling Problems with Mixed No-idle Constraint." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/th4z2d.
Full textAbstract:
碩士國立臺北科技大學
工業工程與管理系碩士班
105
In many times, the companies want to use machines with no-idle. But in practical, considering the cost or technology, and the companies can’t use machines with no-idle. For instance, productions of integrated circuit via photolithography, steel making and fiberglass processing. In recently years, flowshop scheduling has a change in the industry, from a single factory transformed into many factories. More and more companies use flowshop scheduling into their scheduling system. Therefore, this study emphasis on the factory to join the factors and mixed no-idle constraint. The optimization criterion is the minimization of the maximum completion time (Makespan). Therefore , we propose the CTBIG algorithm to solve this problem. The results show that the proposed CTBIG. algorithm is better than the IGPR algorithm.
44
Yang, Sheng-Fa, and 楊盛發. "Two-Machine No-wait Total Tardiness Flowshop Scheduling Problem." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/ugkp89.
Full textAbstract:
碩士朝陽科技大學
工業工程與管理系碩士班
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.
45
Chen, Li-Chiu, and 陳麗秋. "A GA_ENS Algorithm for the Permutation Flowshop Scheduling Problem." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/uubukk.
Full textAbstract:
碩士臺中技術學院
資訊科技與應用研究所
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.
46
LIN, PEI-YU, and 林旆伃. "No-wait Flowshop Scheduling Problems with Specified Release Dates." Thesis, 2019. http://ndltd.ncl.edu.tw/handle/w4ec2b.
Full textAbstract:
碩士國立臺北科技大學
工業工程與管理系
107
In this thesis, we consider the flowshop scheduling problem with no-wait and the given release date constraints for minimizing makespan. For this problem, a mixed-integer linear programming model programming is proposed and programed on LINGO to obtain the optimal solution of small problems, which can be used as a benchmark for the compared algorithm. Moreover, this thesis proposes a Beam Search (BS) algorithm with a local search (BSLS). BS algorithm takes the parameters of beam width and filter width to determine the number of remaining nodes. The efficiency of the BS algorithm would be affected by the number of remaining nodes. To improve the performance of the BS algorithm, the local search is applied. The experimental results show that the BSLS algorithm has a better performance than the BS algorithm among all instances.
47
Tseng, Hsiu-Wen, and 曾秀文. "No-Wait Flowshop Scheduling with Multi-Stage Parallel Machines." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/40903138643192340799.
Full textAbstract:
碩士國立交通大學
工業工程與管理學系
98
This research deals with the problem of N jobs on parallel machines in S successive stages with the constraint that a job after being processed by the first stage’s machine is not allowed the waiting time between two consecutive operations. We call this problem as no-wait flowshop with parallel machines scheduling problem (NWF-P). The objective is to find a schedule that would minimize the makespan. First, considered the machine idle times, we propose an initial solution, named Revised MDA1 and Revised MDA2, for jobs schedule and the assignment of jobs to machines in all stages. Then based on the proposed initial solution, three tabu search algorithms, named TS1, TS2 and TS3, are developed. We evaluate the performances of TS1, TS2 and TS3. with 640 scenarios for experiments. It shows that TS3 is superior to TS1 and TS2 in makespan values and computational time. Finally, considered the tradeoff between machine utilization rates and makespan values, we propose a method to determine the machine numbers in each stage.
48
Chou, ShieChieh, and 周世杰. "Batch Scheduling in a Three-Machine Assembly-Type Flowshop." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/77906722976133127486.
Full textAbstract:
碩士銘傳大學
資訊管理研究所
89
This thesis addresses a three-machine assembly-type flowshop scheduling problem. Machines one and two are fabrication areas arranged as two parallel machines for producing component parts discretely, and machine three is an assembly line arranged as a flowshop for receiving component parts in batches. In this study, we explore useful properties for some special cases and present an NP-hardness proof for a special case. We define a lower bound for solutions to the generic three-machine assembly-type flowshop batch scheduling problem, and then devise several heuristic algorithms and dynamic programming procedures to find approximate solutions. Computational experiments are also conducted to study the effectiveness of the proposed algorithms. Finally, we give some concluding remarks and directions for possible further studies.
49
Hendizadeh, Naini Seyed Hamed. "Scheduling a flowshop manufacturing cell with sequence dependent setup times." 2008. http://hdl.handle.net/1993/20928.
Full text
50
Tsai, Bifang, and 蔡碧芳. "An Approach of Flowshop Scheduling with Identical Parallel Machine Consideration." Thesis, 2003. http://ndltd.ncl.edu.tw/handle/14351441030670309877.
Full textAbstract:
碩士大葉大學
工業工程學系碩士班
91
In this research, an identical parallel machine flowshop scheduling problem in which the dependent setup time is taken into account is considered with minimization of total flowtime. The addressed flowshop scheduling problem is more complex than the traditional flowshop scheduling problems since in the addressed flowshop scheduling problem both machine assignment and job sequencing problems are considered simultaneously. To solve the addressed problem two different solving models are developed. First, a 0-1 integer programming model is constructed; however, the mathematical model is too time consuming to solve the medium or large size problem, thus, a hybrid heuristic which is combined with simulated annealing and tabu search is proposed to get an near optimal schedule in a reasonable computation time. During the research, the parameters used in the heuristics that affect the solution quality and efficiency are analyzed and designed; then for the constructed heuristic, a good parameter setting is suggested. The experimental results are reported, and provided for the references for the further research.