Dissertations / Theses on the topic 'Single Machine Total Tardiness Problem'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 30 dissertations / theses for your research on the topic 'Single Machine Total Tardiness Problem.'
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.
Bauer, Andreas, Bernd Bullnheimer, Richard F. Hartl, and Christine Strauß. "Applying ant colony optimization to solve the single machine total tardiness problem." SFB Adaptive Information Systems and Modelling in Economics and Management Science, WU Vienna University of Economics and Business, 1999. http://epub.wu.ac.at/1368/1/document.pdf.
Full textSeries: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"
Tahboub, Zainel-Abideen Abdul-Majid. "Sequencing to minimize total earliness-tardiness penalties on a single-machine /." The Ohio State University, 1986. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487266362338743.
Full textRODRIGUES, GUSTAVO SIMAO. "SINGLE MACHINE SCHEDULING PROBLEM WITH SEQUENCE DEPENDENT SETUP TIMES, WITH EARLINESS AND TARDINESS PENALTIES: A CASE STUDY IN A MACHINING PROCESS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2012. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=19669@1.
Full textA dissertação estuda o problema do sequenciamento de uma única máquina com tempos de preparação dependentes da sequência da produção e penalidades por antecipação e atraso. Ilustra um método com uma aplicação a um exemplo de processo de fabricação por usinagem. Dessa forma, pretende-se reunir as metodologias de resolução e os trabalhos existentes na literatura sobre o Problema do Sequenciamento e aplicar ao caso específico de um dos Processos de Fabricação mais comuns existentes na indústria.
The dissertation studies the single machine scheduling problem with sequence dependent setup times, with earliness and tardiness penalties, applied to an example of Machining Process Manufacturing. Thus, it is intended to collect the methodologies of resolution and main studies in the literature about the Problem of Sequencing and apply to the specific case of one of the most common manufacturing processes existing in the industry.
Chou, Ying-Chun, and 周盈君. "Variable Neighborhood Search for the Single Machine Total Stepwise Tardiness Problem." Thesis, 2009. http://ndltd.ncl.edu.tw/handle/99771177297163747799.
Full text朝陽科技大學
工業工程與管理系碩士班
97
Over the past scheduling study, all the studies on this subject assume that the tardiness of jobs is a linear tardiness cost function. However, the stepwise tardiness cost function usually exists in many real-life situations, i.e., buyers usually provide several late periods. At the different late periods, firms would pay the different fixed tardiness cost. In this study, the new criterion of scheduling is called stepwise tardiness cost. We will investigate stepwise tardiness criterion in a single machine scheduling problem. First of all, we propose two heuristics to solve the problem. Two heuristics use the SPT and EDD rule as the initial solutions, respectively. In order to obtain good solutions, we also develop a variable neighborhood search (VNS). In VNS algorithm, we develop a new encoding scheme to represent a feasible solution and propose three different neighborhood structures. In particularly, one of the neighborhood structures is based on memory-based mechanism. The experimental results show that the proposed heuristics and VNS algorithm can obtain a good performance for solving this scheduling problem.
"Applying ant colony optimization to solve the single machine total tardiness problem." SFB Adaptive Information Systems and Modelling in Economics and Management Science, 1999. http://epub.wu-wien.ac.at/dyn/dl/wp/epub-wu-01_1dd.
Full textliu, Yi-Ting, and 劉宜婷. "Multiple Variable Neighborhood Search for the Single Machine Total Weighted Tardiness Problem." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/81833659341899050128.
Full text國立臺灣科技大學
工業管理系
98
In recent years, meta-heuristics are common and very popular methods in the industry to solve highly complex problems in different areas, such as production scheduling, logistic distribution, and capacity planning. However, most of the meta-heuristics are too complicated to understand and implement. Therefore, this paper proposes an easy-to-understand meta-heuristic, called multiple Variable Neighborhood Search (m-VNS). The single machine total weighted tardiness (SMTWT) problem is a typical discrete combinatorial optimization problem in the scheduling literature. The m-VNS will be used to solve this well-known problem and compared with several existing famous algorithms. Finally, we found m-VNS algorithm has an excellent performance and is of better results in the solution quality and computational time better than those reported previously in the literature. This research has demonstrated that the m-VNS meta-heuristic can be efficiently and effectively applied to the SMTWT problem.
Chen, Hsia-Hsiang, and 陳夏祥. "Ant Colony System for the Single Machine Total Weighted Tardiness Problem with Sequence-Dependent Setups." Thesis, 2002. http://ndltd.ncl.edu.tw/handle/88275802019118675727.
Full text國立臺灣科技大學
工業管理系
90
Ant colony system (ACS) is one of the most recent meta-heuristics for combinatorial optimization problems. In this paper, an ACS algorithm is proposed for the single machine total weighted tardiness problem with sequence-dependent setup times. To the best of our knowledge, this is the first attempt to propose an improved heuristic, as opposed to the construction heuristic, for this problem. To verify the developed algorithm, computational experiments were conducted on different sizes of problems. The experimental results show that the algorithm find optimal solutions for almost all small size problems. For large size problems, the algorithm significantly improves the best solutions obtained by the construction heuristics. Furthermore, we incorporate different dispatching rules into our ACS algorithm. The results verify that the proposed algorithm is an efficient and effective method for this problem.
Fan, Su-Hao, and 范書豪. "An I Ching optimization for the single machine total weighted tardiness problem with sequence dependent setup times." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/42319073688908857772.
Full textYang, Sheng-Fa, and 楊盛發. "Two-Machine No-wait Total Tardiness Flowshop Scheduling Problem." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/ugkp89.
Full text朝陽科技大學
工業工程與管理系碩士班
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.
Gonçalves, Tomás Cabrita. "Two Metaheuristics for the Single-Machine Quadratic Tardiness Scheduling Problem." Master's thesis, 2012. https://repositorio-aberto.up.pt/handle/10216/66535.
Full textGonçalves, Tomás Cabrita. "Two Metaheuristics for the Single-Machine Quadratic Tardiness Scheduling Problem." Dissertação, 2012. https://repositorio-aberto.up.pt/handle/10216/66535.
Full textJhong, Cheng-Ruei, and 鍾承叡. "Two-Machine Flow Shop Scheduling Problem with Blocking for Minimizing Total Tardiness." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/73946716093643842354.
Full text國立中央大學
工業管理研究所
102
This paper considers a flow shop scheduling problem with blocking where the objective is to minimize total tardiness. There are two machines and n jobs, each job has different due date and the sequence of job is decided by machine 1. In two-machine flow shop with blocking scheduled problem, there are zero capacity buffer between machines and the job of completing is block on machine until the next downstream machine is available. The total tardiness will increase by influence of blocking constraint. We use branch and bound algorithm to find out an optimal sequence and propose five dominance criteria which are decide jobs of the precedence in an optimal schedule. For bounding, we extend lower bound of Pan, Chen and Chao (2002) to improve the branch and bound algorithm. In computation experiment, we use four scenarios of Ronconi and Armentano (2001) to test our algorithm. In job size between 10 and 18, our algorithm branches out fewer number of nodes as compared to the result in Ronconi and Armentano (2001).
Wang, Yow-ru, and 汪祐如. "Single machine scheduling problem－considering the earliness-tardiness penalty and delivery cost." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/15868965853832771694.
Full text國立雲林科技大學
工業工程與管理研究所碩士班
94
For manufacturing industry, the order begins from the moment that the factory gets it, then proceeds to production and ends when the comapany deliver the goods to customers. When we consider the scheduling problem, we should consider scheduling of order processing and scheduling of order delivery in the same time. But the two parts do not independent, it means when we decide one of them that will be affect the other one. WTO opens globalization market competiton. Cooperating with other countries is more frequently and delivery cost takes a bigger part in the cost structure. Single customer may asks different due date with different jobs. In order to reduce delivery cost、satisfy the due date and consider earliness penalty, so we should think the scheduling of order processing and scheduling of order delivery in the same time. Our research sets up a model that integrates order schedule and delivery schedule, by mathematic programming at first. But the problem is a NP-hard, computation time increases exponentially as number of orders grows. So our research develops methods of two stages and delivery algorithm. And by the results of experiment, our methods could solve the problem with abundance of orders in shorter time and the solutions are close to optimal.
Yu-Ling, Lai, and 賴郁玲. "Genetic algorithm for single-machine scheduling to minimize total tardiness with the minimize total tardiness with the minmize number of tardy jobs." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/99459678579447277102.
Full textHu, Mei-Chia, and 胡美佳. "Single-machine two-agent scheduling to minimize the total tardiness with release time." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/55551843833370687059.
Full text逢甲大學
統計與精算所
100
The needs of customers are different under limited labor power, resourses and cost control. It will be more effective if we plan ahead. In recent years, the scheduling problems with two competing agents have become more popular. In this paper, we studied a single-machine scheduling problem with release time where the objective is to minimize the total tardiness of jobs from the first agent given that the maximum tardiness of jobs from the second agent does not exceed an upper bound. A branch-and-bound algorithm is developed to search for the optimal solution. In addition, genetic algorithm are proposed to obtain the near-optimal solutions. Computational experiments are conducted to evaluate the performance of the proposed branch-and-bound algorithm and the genetic algorithms. Statistical tests are also performed to study the impact of the parameters.
WEN, TSAI CHIH, and 蔡誌文. "Hybrid Genetic Algorithm for Single-Machine Scheduling Problem with Earliness and Tardiness Costs." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/89547421471388638336.
Full text莊許鑫. "Scheduling to Minimize Expected Total Tardiness Penalties and Earliness Cost in a Single Machine." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/89806064228044563522.
Full text邱欽鴻. "A simulated annealing approach for the two-machine total earliness and tardiness scheduling problem." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/20691155067201739678.
Full textSambuchetti, James Teddy Limousin. "Heuristics for the single machine weighted quadratic tardiness scheduling problem with unequal release date." Master's thesis, 2018. https://hdl.handle.net/10216/113385.
Full textSambuchetti, James Teddy Limousin. "Heuristics for the single machine weighted quadratic tardiness scheduling problem with unequal release date." Dissertação, 2018. https://hdl.handle.net/10216/113385.
Full textLiu, Chih-Yu, and 劉芷羽. "Single-machine scheduling to minimize the total completion time and tardiness with two competing agents." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/20920977425406159548.
Full text逢甲大學
統計與精算所
100
Scheduling with two competing agents has become a popular research topic in recent years. Most of the research focuses on the objective functions with constraint forms, that is, to minimize the objective function of jobs from one agent given that the objective function of jobs from the other agent does not exceed an upper bound. In this paper, we consider a different approach for a two-agent problem on a single machine. The objective is the weighted sum of the total completion time of jobs from one agent and the total tardiness of jobs from the other agent. Two branch-and-bound algorithms are proposed to derive the optimal sequences. In addition, a simulated annealing and two genetic algorithms are provided to search for the near-optimal solutions. Computational experiments show that the proposed branch-and branch algorithm could solve problems of up to 40 jobs in a reasonable amount of time and the genetic algorithm that use initial sequence is good with an average error percentage of less then 1.5% for all the tested cases.
Ding, Lawson, and 丁浩. "Two-agent scheduling on a single machine to minimize the total completion time and tardiness." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/66575273597552673039.
Full text逢甲大學
統計與精算所
99
Often a decision maker has to decide the schedule based on multiple criteria. On the other hand, jobs might be from several customers which have their different goals to pursue. In this paper, we consider a single machine two-agent problem where the objective is to minimize a weighted combination of the total completion time and the total tardiness of jobs from the first agent subject to the constraint that no tardy jobs are allowed for the second agent. A branch-and-bound algorithm is developed to derive the optimal sequence and two simulated annealing heuristic algorithms are proposed to search for the near-optimal solutions. Computational experiments are also conducted to evaluate the proposed branch-and-bound and simulated annealing algorithms.
温志皓. "Minimizing the total tardiness on a two-machine flowshop scheduling problem with a precedence constraint." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/22806786859545697294.
Full text逢甲大學
統計學系統計與精算碩士班
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.
Huang, Zong-Ren, and 黃宗仁. "A single machine scheduling to minimize the total completion time and maximum tardiness with two agents." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/14373980932375400144.
Full text逢甲大學
統計與精算所
99
The multiple-agent scheduling problems have received increasing attention recently. However, most of the research focuses on studying the computational complexity of the intractable cases or examining problems with a single criterion. Often a decision maker has to decide the schedule based on multiple criteria. In this paper, we consider a single machine problem where the objective is to minimize a linear combination of the total completion time and the maximum tardiness of jobs from the first agent given that no tardy jobs are allowed for the second agent. We develop a branch-and-bound algorithm and several simulated annealing algorithms to search for the optimal solution and near-optimal solutions for the problem, respectively. Computational experiments show that the proposed branch-and-bound algorithm could solve problems of up to 24 jobs in a reasonable amount of time and the performance of the combined simulated annealing algorithm is very good with an average error percentage of less than 0.5% for all the tested cases.
Chen, Che-Yu, and 陳哲宇. "A Tabu Search Algorithm for The Two-Machine Preemptive Open Shop Problem to Minimize Total Tardiness." Thesis, 2002. http://ndltd.ncl.edu.tw/handle/44488741197252173735.
Full text朝陽科技大學
工業工程與管理系碩士班
90
The preemptive open shop scheduling problem with the objective of minimizing total tardiness is a NP-hard problem. An open shop can be defined as follows：a set of jobs must be processed by a set of machines where both the order of jobs processed on each machine and the order of machines visited by each job can be chosen arbitrarily. Each machine can process at most one job at a time and each job can be processed exactly on one machine at a time. We consider the preemptive case；that is, the processing of any job on any machine may arbitrarily often be interrupted and resumed later without penalty. In this research, we develop an approximation algorithm for solving the two-machine preemptive open shop scheduling problem with the objective of minimizing total tardiness. The algorithm is based on the tabu search technique. Tabu search, a local search method for combinatorial optimization problem, has been successfully applied to a variety of scheduling problems. The tabu search algorithm developed in this research can find optimal or near optimal solutions for large sized problems within a reasonable amount of CPU time. Statistical tests are conducted to determine the best parameters for the tabu search algorithm. Computational experiments show that the proposed tabu search algorithm performs extremely well. For small sized problems the solutions’ quality is evaluated against optimal solution value, while for large sized problems the tabu search algorithm is compared with a heuristic algorithm proposed in the literature.
Huang, Yi-Chi, and 黃依琪. "A single-machine scheduling problem to minimize the maximum tardiness with deteriorating jobs and setup times." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/32322655109112968846.
Full text逢甲大學
統計與精算所
98
In many realistic production situations, a job processed later consumes more time than the same job when it is processed earlier. Production scheduling in such an environment is known as scheduling with deteriorating jobs. However, research on scheduling problems with deteriorating jobs has rarely considered explicit (separable) setup time (cost). In this paper we consider a single-machine scheduling problem with deteriorating jobs and setup times to minimize the maximum tardiness. We provide a branch-and-bound algorithm to solve this intractable problem. Computational experiments show that the algorithm can solve instances up to 1,000 jobs in a reasonable amount of time.
Lu, Chia-Jung, and 呂佳容. "A Heuristic Algorithm for Total Weighted Tardiness Minimization on Parallel-Machine Scheduling Problem - A Case of Biotechnology Product Line." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/3csxc7.
Full text中原大學
工業工程研究所
101
This research focuses on the scheduling problem of identical parallel machines to minimize the total tardiness. Each order has several different items, arrival time, weightings, and delivery time while each item of the order has the same arrival time, weighting, and delivery time. The finish time of each order is determined by the finish time of the last item in it. In the research an innovative heuristic meathod is developed to obtain an accepted answer and compares with methods used before. For the scheduling problem of procedural sepuence factory from ordering material to complete finishing, by taking the production character of the industry into account, we consider postponing finishing one work to delivery date, and then the next and the after work may be done early to decrease the tardiness or possibility of delay. The purpose of this research is to find out the tailor-made scheduling system for delivery.
Su, Hsin-wei, and 蘇信維. "An advanced genetic algorithm for single-machine scheduling to minimize the total tardiness with learning effects and two competing agents." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/71739847217305049151.
Full textChen, Hung-Ming, and 陳弘明. "A study of the single-machine total late work scheduling problem with learning consideration." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/80525001255003354040.
Full text逢甲大學
統計與精算所
99
Scheduling with learning effects has received a lot of research attention lately. On the other hand, it is common seen that time restrictions are usually modeled by due dates or deadlines and the quality of schedules is estimated with reference to these parameters. One of the performance measures involving due dates is the late work criterion, which is relatively unexplored. Thus, we study a single-machine scheduling problem with a position-based learning effect. The objective is to minimize the total late work, where the late work for a job is the amount of processing of this job that is performed after its due date. Since the complexity of the proposed problem is NP-hard , we attempt to develop a branch-and-bound algorithm incorporating with some dominance rules and a lower bound for the optimal solution. For the saving computational time, we also propose six simulated annealing heuristic algorithms for the near-optimal solution. Finally, the computational results of proposed algorithms are also provided.
Wei-Liang, Chao, and 趙文涼. "Single Machine Scheduling Problem Subject to Minimization of Total Absolute Deviation and Setup Cost by Genetic Algorithm." Thesis, 2001. http://ndltd.ncl.edu.tw/handle/64687316084651827739.
Full text元智大學
工業工程研究所
89
With the changing of production types, taking setup time into consideration is getting more and more important for industrial schedulers. Therefore, in this research, we explores the single machine scheduling problem with minimizing the total absolute deviation and setup cost where setup times are sequence dependent. Genetic algorithm is applied to search the optimal or near-optimal solutions in this research owing to its outstanding parallel searching capability. Moreover, through experimental design and statistical analysis, genetic algorithm is verified to receive comparative improvement. Besides the above-mentioned results, this research investigates the optimal designs of parameters used in the genetic algorithm. We discuss the effect of number of chromosomes per population, crossover rate, mutation rate, number of generations and propose the difference between variable mutation rate and fixed mutation rate. Algorithm with variable mutation rate results in superior solutions, but it is difficult to convergent state. On the other hand, the convergence of fixed mutation rate is superior to variable mutation rate, and the solution quality is more robust than variable mutation rate.