No description available.

Ant Colony Optimization is a relatively new meta-heuristic that has proven its quality and versatility on various combinatorial optimization problems such as the traveling salesman problem, the vehicle routing problem and the job shop scheduling problem. The paper introduces an Ant Colony Optimization approach to solve the problem of determining a job-sequence that minimizes the overall tardiness for a given set of jobs to be processed on a single, continuously available machine, the Single Machine Total Tardiness Problem. We experiment with various heuristic information as well as with variants for local search. Experiments with 250 benchmark problems with 50 and 100 jobs illustrate that Ant Colony Optimization is an adequate method to tackle the SMTTP. (author's abstract) / Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

Hundreds of steel products need to be scheduled on a single or parallel machine in a steel plant every week. A good feasible schedule may save the company millions of dollars compared to a bad one. Single and parallel machine scheduling are also encountered often in many other industries, making it a crucial research topic for both the process system engineering and operations research communities. Single or parallel machine scheduling can be a challenging combinatorial optimization problem when a large number of jobs are to be scheduled. Each job has unique job characteristics, resulting in different setup times/costs depending on the processing sequence. They also have specific release dates to follow and due dates to meet. This work presents both an exact method using mixed-integer quadratic programming, and an approximate method with metaheuristics to solve real-world large-scale single/parallel machine scheduling problems faced in a steel plant. More than 1000 or 350 jobs are to be scheduled within a one-hour time limit in the single or parallel machine problem, respectively. The objective of the single machine scheduling is to minimize a combined total changeover, total earliness, and total tardiness cost, whereas the objective of the parallel machine scheduling is to minimize an objective function comprising the gaps between jobs before a critical time in a schedule, the total changeover cost, and the total tardiness cost. The exact method is developed to benchmark computation time for a small-scale single machine problem, but is not practical for solving the actual large-scale problem. A metaheuristic algorithm centered on variable neighborhood descent is developed to address the large-scale single machine scheduling with a sliding-window decomposition strategy. The algorithm is extended and modified to solve the large-scale parallel machine problem. Statistical tests, including Student's t-test and ANOVA, are conducted to determine efficient solution strategies and good parameters to be used in the metaheuristics. / Thesis / Master of Applied Science (MASc)

No description available.

In manufacturing environments, machines are usually subject to down periods due to various reasons such as preventive maintenance activities, pre-accepted jobs and pre-known material shortages. Among these reasons, preventive maintenance, which is defined as the pre-planned maintenance activities to keep the machine in its operating state, has gained much more importance in recent years. In this thesis, we consider the single machine total flow time problem where the jobs are non-resumable and the machine is subject to preventive maintenance activities of known starting times and durations. We propose a number of optimality properties together with the upper and lower bounding procedures. Using these mechanisms, we build a branch and bound algorithm to find the optimal solution of the problem. Our extensive computational study on randomly generated test instances shows that our algorithm can solve large-sized problem instances with up to 80 jobs in reasonable times. We also study a two-alternative maintenance planning problem with minor and major maintenances. We give an optimizing algorithm to find the timing of the maintenances, when the job sequence is fixed.

ABSTRACT A HEURISTIC APPROACH FOR THE SINGLE MACHINE SCHEDULING TARDINESS PROBLEMS &Ouml / zbakir, Saffet Ilker M.Sc., Department of Industrial Engineering Supervisor : Prof. Dr. &Ouml / mer Kirca September 2011, 102 pages In this thesis, we study the single machine scheduling problem. Our general aim is to schedule a set of jobs to the machine with a goal to minimize tardiness value. The problem is studied for two objectives: minimizing total tardiness value and minimizing total weighted tardiness value. Solving optimally this problem is difficult, because both of the total tardiness problem and total weighted tardiness problem are NP-hard problems. Therefore, we construct a heuristic procedure for this problem. Our heuristic procedure is divided to two parts: construction part and improvement part. The construction heuristic is based on grouping the jobs, solving these groups and then fixing some particular number of jobs. Moreover, we used three type improvement heuristics. These are sliding forward method, sliding backward method and pairwise interchange method. Computational results are reported for problem size = 20, 40, 50 and 100 at total tardiness problem and for problem size = 20 and 40 at total weighted tardiness problem. Experiments are designed in order to investigate the effect of three factors which are problem size, tardiness factor and relative range of due dates on computational difficulties of the problems. Computational results show that the heuristic proposed in this thesis is robust to changes at these factors.

This study focuses on the study of a unique but commonly occurring manufacturing problem of scheduling of customized jobs consisting of two operations on a single multi-purpose machine with the performance objective of minimizing the number of tardy jobs (jobs that are not completed by their due dates). Each customized job to be complete needs one unique operation and one common operation performed on it. We considered a static case in this work. The objective of minimizing the number of tardy jobs is considered where all jobs have equal weights and the maximum tardiness has no effect on the performance. This problem is proved in literature as NP-hard and hence practically very difficult to obtain optimal solution within reasonable computational time. Till date only a pseudo-polynomial algorithm is given to solve this problem with no concrete computational experiments designed to prove the efficiency and working of the algorithm for different problem instances. We propose a heuristic algorithm based on the Moore-Hodgson's algorithm combining with other procedures and optimal schedule properties from the literature to solve this problem. In literature, Moore-Hodgson's algorithm is an efficient heuristic algorithm that minimizes the number of tardy jobs for the classical single machine one-operation problems. The performance of the heuristic is evaluated through extensive computational experiments for large real size data. The obtained results are compared to the solutions obtained by implementing the optimal pseudo-polynomial algorithm and the performance of the heuristic is tested on large data sets. The test data for the computational experiments are generated randomly using MATLAB 6.1. Future directions of research and development on the problem to improve the obtained solution by the heuristic algorithm are given.

No description available.

Majority of the studies in the scheduling literature is devoted to time based performance measures. In this thesis, we develop a model that considers monetary issues in single machine scheduling environments. We assume all the jobs should be completed by a common due date. An early revenue is earned if the completion time is before or on the due date, and a tardy revenue is gained if the job is completed after the due date. We consider restricted and unrestricted due date versions of the problem. Our objective is the maximization of the net present value of all revenues. We first investigate some special cases of the problem, and present polynomial time algorithms to solve them. Then, we develop branch and bound algorithms with lower and upper bounding mechanisms. Computational experiments have shown that the branch and bound algorithms can solve large-sized problems in reasonable times.

In this paper we propose an improved algorithm to search optimal solutions to the single machine total weighted tardiness scheduling problem. We propose using longest common sequence to combine with the random key method. Numerical simulation shows that the scheme we proposed could improve the search efficiency of genetic algorithm in this problem for some cases.