A tabu search algorithm for the single machine total weighted tardiness problem

In this study, a tabu search (TS) approach to the single machine total weighted tardiness problem (SMTWT) is presented. The problem consists of a set of independent jobs with distinct processing times, weights and due dates to be scheduled on a single machine to minimize total weighted tardiness. The theoretical foundation of single machine scheduling with due date related objectives reveal that the problem is NP-hard, rendering it a challenging area for meta-heuristic approaches. This paper presents a totally deterministic TS algorithm with a hybrid neighborhood and dynamic tenure structure, and investigates the strength of several candidate list strategies based on problem specific characteristics in increasing the efficiency of the search. The proposed TS approach yields very high quality results for a set of benchmark problems obtained from the literature.     

A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times

In this paper we present a new Discrete Particle Swarm Optimization (DPSO) approach to face the NP-hard single machine total weighted tardiness scheduling problem in presence of sequence-dependent setup times. Differently from previous approaches the proposed DPSO uses a discrete model both for particle position and velocity and a coherent sequence metric. We tested the proposed DPSO mainly over a benchmark originally proposed by Cicirello in 2003 and available online. The results obtained show the competitiveness of our DPSO, which is able to outperform the best known results for the benchmark. In addition, we also tested the DPSO on a set of benchmark instances from ORLIB for the single machine total weighted tardiness problem, and we analysed the role of the DPSO swarm intelligence mechanisms as well as the local search intensification phase included in the algorithm.     

A memetic algorithm for the total tardiness single machine scheduling problem

In this paper, a new memetic algorithm (MA) for the total tardiness single machine scheduling (SMS) problem with due dates and sequence-dependent setup times is proposed. The main contributions with respect to the implementation of the hybrid population approach are a hierarchically structured population conceived as a ternary tree and the evaluation of three recombination operators. Concerning the local improvement procedure, several neighborhood reduction schemes are developed and proved to be effective when compared to the complete neighborhood. Results of computational experiments are reported for a set of randomly generated test problems. The memetic approach and a pure genetic algorithm (GA) version are compared with a multiple start algorithm that employs the all-pairs neighborhood as well as two constructive heuristics.     

Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process

We consider a scheduling problem in a factory producing printed circuit boards (PCBs). The PCB assembly process in this factory can be regarded as a flowshop which has two special characteristics: jobs have sequence dependent setup times and each job consists of a lot (batch) of identical PCBs. Because of the latter characteristic, it is possible to start a job on a following machine before the job is entirely completed on a previous machine, that is, there is time-lag between machines. In this paper, we propose several heuristics, including taboo search (TS) and simulated annealing (SA) methods, for this generalized flowshop scheduling problem with the objective of minimizing mean tardiness. We compare suggested heuristics after series of tests to find appropriate values for parameters needed for the two search algorithms, TS and SA. Results of computational tests on randomly generated test problems are reported.     

Meta-heuristic approaches for minimizing total earliness and tardiness penalties of single-machine scheduling with a common due date

This study addresses a class of single-machine scheduling problems involving a common due date where the objective is to minimize the total job earliness and tardiness penalties. A genetic algorithm (GA) approach and a simulated annealing (SA) approach utilizing a greedy local search and three well-known properties in the area of common due date scheduling are developed. The developed algorithms enable the starting time of the first job not at zero and were tested using a set of benchmark problems. From the viewpoints of solution quality and computational expenses, the proposed approaches are efficient and effective for problems involving different numbers of jobs, as well as different processing time, and earliness and tardiness penalties.     

Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times

We compare several heuristics for solving a single machine scheduling problem. In the operating situation modelled, setup times are sequence-dependent and the objective is to minimize total tardiness. We describe an Ant Colony Optimization (ACO) algorithm having a new feature using look-ahead information in the transition rule. This feature shows an improvement in performance. A comparison with a genetic algorithm, a simulated annealing approach, a local search method and a branch-and-bound algorithm indicates that the ACO that we describe is competitive and has a certain advantage for larger problems.     

A dispatching algorithm for parallel machines with rework processes

This paper presents a parallel machine scheduling problem with rework probabilities, due-dates and sequence-dependent setup times. It is assumed that rework probability for each job on a machine can be given through historical data acquisition. Since the problem is NP-hard in the strong sense, a heuristic algorithm is presented, which finds good solutions. The dispatching algorithm named MRPD (minimum rework probability with due-dates) is proposed in this paper focusing on the rework processes. The performance of MRPD is measured by the six diagnostic indicators: total tardiness, maximum lateness, mean flow-time, mean lateness, the number of reworks and the number of tardy jobs. A large number of test problems are randomly generated to evaluate the performance of the proposed algorithm. Computational results show that the proposed algorithm is significantly superior to existing dispatching algorithms for the test problems.     

Increasing the total net revenue for single machine order acceptance and scheduling problems using an artificial bee colony algorithm

The order acceptance and scheduling (OAS) problem is an important topic for make-to-order production systems with limited production capacity and tight delivery requirements. This paper proposes a new algorithm based on Artificial Bee Colony (ABC) for solving the single machine OAS problem with release dates and sequence-dependent setup times. The performance of the proposed ABC-based algorithm was validated by a benchmark problem set of test instances with up to 100 orders. Experimental results showed that the proposed ABC-based algorithm outperformed three state-of-art metaheuristic-based algorithms from the literature. It is believed that this study successfully demonstrates a high-performance algorithm that can serve as a new benchmark approach for future research on the OAS problem addressed in this study.

     

Scatter search for minimizing weighted tardiness in a single machine scheduling with setups

Single machine scheduling problems have many real-life applications and may be hard to solve due to the particular characteristics of some production environments. In this paper, we tackle the single machine scheduling problem with sequence-dependent setup times with the objective of minimizing the weighted tardiness. To solve this problem, we propose a scatter search algorithm which uses path relinking in its core. This algorithm is enhanced with some procedures to speed-up the neighbors’ evaluation and with some diversification and intensification techniques, the latter taking some elements from iterated local search. We conducted an experimental study across a well-known set of instances to analyze the contribution of each component to the overall performance of the algorithm, as well as to compare our proposal with the state-of-the-art metaheuristics, obtaining competitive results. We also propose a new benchmark with larger and more challenging instances and provide the first results for them.     

Comparative analysis of three metaheuristics for short-term open pit block sequencing

This paper presents the application of simulated annealing (SA), Tabu search (TS) and hybrid TS–SA to solve a real-world mining optimisation problem called open pit block sequencing (OPBS). The OPBS seeks the optimum extraction sequences under a variety of geological and technical constraints over short-term horizons. As industry-scale OPBS instances are intractable for standard mixed integer programming (MIP) solvers, SA, TS and hybrid TS–SA are developed to solve the OPBS problem. MIP exact solution is also combined with the proposed metaheuristics to polish solutions in feasible neighbourhood moves. Extensive sensitivity analysis is conducted to analyse the characteristics and determine the optimum sets of values of the proposed metaheuristics algorithms’ parameters. Computational experiments show that the proposed algorithms are satisfactory for solving the OPBS problem. Additionally, this comparative study shows that the hybrid TS–SA is superior to SA or TS in solving the OPBS problem in several aspects.     

A bicriteria parallel machine scheduling with a learning effect of setup and removal times

In studies on scheduling problems, generally setup times and removal times of jobs have been neglected or by including those into processing times. However, in some production systems, setup times and removal times are very important such that they should be considered independent from processing times. Since, in general jobs are done according to automatic machine processes in production systems processing times do not differ according to process sequence. But, since human factor becomes influential when setup times and removal times are taken into consideration, setup times will be decreasing by repeating setup processes frequently. This fact is defined with learning effect in scheduling literature. In this study, a bicriteria m-identical parallel machines scheduling problem with a learning effect of setup times and removal times is considered. The objective function of the problem is minimization of the weighted sum of total completion time and total tardiness. A mathematical programming model is developed for the problem which belongs to NP-hard class. Results of computational tests show that the proposed model is effective in solving problems with up to 15 jobs and five machines. We also proposed three heuristic approaches for solving large jobs problems. According to the best of our knowledge, no work exists on the minimization of the weighted sum of total completion time and total tardiness with a learning effect of setup times and removal times.     

Single machine scheduling with family setups to minimize total earliness and tardiness

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize total earliness and tardiness when family setup times exist. The paper proposes optimal branch-and-bound algorithms for both the group technology assumption and if the group technology assumption is removed. A heuristic algorithm is proposed to solve larger problems with the group technology assumption removed. The proposed algorithms were empirically evaluated on problems of various sizes and parameters. The paper also explores how the choice of procedure affects total earliness and tardiness if an implementation of lean production methods has resulted in a reduction in setup times. An important finding of these empirical investigations is that scheduling jobs by removing the group technology assumption can significantly reduce total earliness and tardiness.     

Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions

The capacitated lot sizing and loading problem (CLSLP) deals with the issue of determining the lot sizes of product families/end items and loading them on parallel facilities to satisfy dynamic demand over a given planning horizon. The capacity restrictions in the CLSLP are imposed by constraints specific to the production environment considered. When a lot size is positive in a specific period, it is loaded on a facility without exceeding the sum of the regular and overtime capacity limits. Each family may have a different process time on each facility and furthermore, it may be technologically feasible to load a family only on a subset of existing facilities. So, in the most general case, the loading problem may involve unrelated parallel facilities of different classes. Once loaded on a facility, a family may consume capacity during setup time. Inventory holding and overtime costs are minimized in the objective function. Setup costs can be included if setups incur costs other than lost production capacity. The CLSLP is relevant in many industrial applications and may be generalized to multi-stage production planning and loading models. The CLSLP is a synthesis of three different planning and loading problems, i.e., the capacitated lot sizing problem (CLSP) with overtime decisions and setup times, minimizing total tardiness on unrelated parallel processors, and, the class scheduling problem, each of which is NP in the feasibility and optimality problems. Consequently, we develop hybrid heuristics involving powerful search techniques such as simulated annealing (SA), tabu search (TS) and genetic algorithms (GA) to deal with the CLSLP. Results are compared with optimal solutions for 108 randomly generated small test problems. The procedures developed here are also compared against each other in 36 larger size problems.     

Minimizing total tardiness in parallel machine scheduling with setup times: An adaptive memory-based GRASP approach

This paper deals with the problem of scheduling jobs in uniform parallel machines with sequence-dependent setup times in order to minimize the total tardiness relative to job due dates. We propose GRASP versions that incorporate adaptive memory principles for solving this problem. Long-term memory is used in the construction of an initial solution and in a post-optimization procedure which connects high quality local optima by means of path relinking. Computational tests are carried out on a set of benchmark instances and the proposed GRASP versions are compared with heuristic methods from the literature.     

基于PSO-MAs算法的产品组合问题研究

针对多约束的产品组合问题,提出一种基于PSO的Memetic算法。该算法首先运用约束理论识别并剔除非瓶颈约束,然后基于伪效用比率设计了一个局部搜索算法,并将其加入到PSO算法的种群进化中,以增强PSO算法的局部学习能力。通过对算法在小规模和大规模算例中测试,表明该算法在小规模问题中优于许多已有算法,同时能在相对较短地时间内更有效地求解较大规模产品组合问题。因此本文提出的基于PSO的Memetic算法可以用来有效地求解实际中的产品组合问题。     

Pricing,relaxing and fixing under lot sizing and scheduling

We present a novel mathematical model and a mathematical programming based approach to deliver superior quality solutions for the single machine capacitated lot sizing and scheduling problem with sequence-dependent setup times and costs. The formulation explores the idea of scheduling products based on the selection of known production sequences. The model is the basis of a matheuristic, which embeds pricing principles within construction and improvement MIP-based heuristics. A partial exploration of distinct neighborhood structures avoids local entrapment and is conducted on a rule-based neighbor selection principle. We compare the performance of this approach to other heuristics proposed in the literature. The computational study carried out on different sets of benchmark instances shows the ability of the matheuristic to cope with several model extensions while maintaining a very effective search. Although the techniques described were developed in the context of the problem studied, the method is applicable to other lot sizing problems or even to problems outside this domain.     

A branch-and-bound algorithm of the single machine schedule with sequence-dependent setup times for minimizing maximum tardiness

This paper addresses the NP-hard problem of scheduling N jobs on a single machine with due dates, sequence-dependent setup times and no preemption where the objective is to minimize the maximum tardiness. An algorithm based on branch-and-bound permutation schemes is developed including the implementation of lower and upper bounding procedures, and three dominance rules. Computational experiments demonstrate the effectiveness of the algorithm. In the experiments, the impacts of control parameters to generate test instances on algorithm performance (CPU times) are studied by statistics methods.     

Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm

Relative to job-shop scheduling problems that optimize makespan or flow time, due-date-related problems are usually much more computationally complex and are classified as strongly NP-hard. In this paper, a hybrid framework integrating a heuristic and a genetic algorithm (GA) is utilized for job-shop scheduling to minimize weighted tardiness. For each new generation of schedules, the GA determines the first operation of each machine, and the heuristic determines the assignment of the remaining operations. Schedules with inferior tardiness are discarded before the next round of evolution. Extensive numerical experiments were conducted for different levels of due-date tightness. The results show that the hybrid framework performs significantly better than does either a heuristic or GA alone. It is also found to be superior to a well-recognized heuristic improvement procedure (lead-time iterations). Specifically, the combination of the R&M heuristic and a GA outperforms a number of heuristics commonly used to minimize total tardiness and weighted total tardiness; this combination is, however, outperformed by the heuristic of Kreipl [Kreipl, S., 2000. A large step random walk for minimizing total weighted tardiness in a job shop. Journal of Scheduling 3, 125–138]. We also develop a generalized hybrid framework that can adapt to different job-shop problems—with or without sequence-dependent setups and with different objectives (e.g., makespan, tardiness, flow time). The new framework allows the interaction of parallel evolutions, extending the GA-heuristic environment to the solving of multi-objective scheduling problems.     

Minimizing the sum of maximum earliness and maximum tardiness in the single-machine scheduling problem with sequence-dependent setup time

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize the sum of maximum earliness and maximum tardiness when sequence-dependent setup times exist (1∣ST _sd ∣ET_max). In this paper, an optimal branch-and-bound algorithm is developed that involves the implementation of lower and upper bounding procedures as well as three dominance rules. For solving problems containing large numbers of jobs, a polynomial time-bounded heuristic algorithm is also proposed. Computational experiments demonstrate the effectiveness of the bounding and dominance rules in achieving optimal solutions in more than 97% of the instances.     

Metaheuristic algorithms for balancing robotic assembly lines with sequence-dependent robot setup times

Industries are incorporating robots into assembly lines due to their greater flexibility and reduced costs. Most of the reported studies did not consider scheduling of tasks or the sequence-dependent setup times in an assembly line, which cannot be neglected in a real-world scenario. This paper presents a study on robotic assembly line balancing, with the aim of minimizing cycle time by considering sequence-dependent setup times. A mathematical model for the problem is formulated and CPLEX solver is utilized to solve small-sized problems. A recently developed metaheuristic Migrating Birds Optimization (MBO) algorithm and set of metaheuristics have been implemented to solve the problem. Three different scenarios are tested (with no setup time, and low and high setup times). The comparative experimental study demonstrates that the performance of the MBO algorithm is superior for the tested datasets. The outcomes of this study can help production managers improve their production system in order to perform the assembly tasks with high levels of efficiency and quality.