A hybrid Lagrangian-simulated annealing-based heuristic for the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times

This paper examines the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times, time windows, machine eligibility and preference constraints. Such problems are quite common in the semiconductor manufacturing industry. In particular, this paper pays special attention to the chipset production in the semiconductor Assembly and Test Manufacturing (ATM) factory and constructs a Mixed Integer Programming (MIP) model for the problem. The primal problem is decomposed into a lot-sizing subproblem and a set of single-machine scheduling subproblems by Lagrangian decomposition. A Lagrangian-based heuristic algorithm, which incorporates the simulated annealing algorithm aimed at searching for a better solution during the feasibility construction stage, is proposed. Computational experiments show that the proposed hybrid algorithm outperforms other heuristic algorithms and meets the practical requirement for the tested ATM factory.     

Multi-agent based approach for single machine scheduling with sequence-dependent setup times and machine maintenance

Scheduling of single machine in manufacturing systems is especially complex when the order arrivals are dynamic. The complexity of the problem increases by considering the sequence-dependent setup times and machine maintenance in dynamic manufacturing environment. Computational experiments in literature showed that even solving the static single machine scheduling problem without considering regular maintenance activities is NP-hard. Multi-agent systems, a branch of artificial intelligence provide a new alternative way for solving dynamic and complex problems. In this paper a collaborative multi-agent based optimization method is proposed for single machine scheduling problem with sequence-dependent setup times and maintenance constraints. The problem is solved under the condition of both regular and irregular maintenance activities. The solutions of multi-agent based approach are compared with some static single machine scheduling problem sets which are available in the literature. The method is also tested under real-time manufacturing environment where computational time plays a critical role during decision making process.     

MIP formulation and heuristics for multi-stage capacitated lot-sizing and scheduling problem with availability constraints

In this paper, the problem of lot-sizing and scheduling of multiple product types in a capacitated flow shop with availability constraints for multi-period planning horizon is considered. In many real production systems, machines may be unavailable due to breakdowns or preventive maintenance activities, thus integrating lot-sizing and scheduling with maintenance planning is necessary to model real manufacturing conditions. Two variants are considered to deal with the maintenance activities. In the first, the starting times of maintenance tasks are fixed, whereas in the second one, maintenance must be carried out in a given time window. A new mixed-integer programming (MIP) model is proposed to formulate the problem with sequence-dependent setups and availability constraints. The objective is to find a production and preventive maintenance schedule that minimizes production, holding and setup costs. Three MIP-based heuristics with rolling horizon framework are developed to generate the integrated plan. Computational experiments are performed on randomly generated instances to show the efficiency of the heuristics. To evaluate the validity of the solution methods, problems with different scales have been studied and the results are compared with the lower bound. Computational experiments demonstrate that the performed methods have good-quality results for the test problems.     

A study of hybrid evolutionary algorithms for single machine scheduling problem with sequence-dependent setup times

We present a systematic comparison of hybrid evolutionary algorithms (HEAs), which independently use six combinations of three crossover operators and two population updating strategies, for solving the single machine scheduling problem with sequence-dependent setup times. Experiments show the competitive performance of the combination of the linear order crossover operator and the similarity-and-quality based population updating strategy. Applying the selected HEA to solve 120 public benchmark instances of the single machine scheduling problem with sequence-dependent setup times to minimize the total weighted tardiness widely used in the literature, we achieve highly competitive results compared with the exact algorithm and other state-of-the-art metaheuristic algorithms in the literature. Meanwhile, we apply the selected HEA in its original form to deal with the unweighted 64 public benchmark instances. Our HEA is able to improve the previous best known results for one instance and match the optimal or the best known results for the remaining 63 instances in a reasonable time.     

A note on “the capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times

Gupta and Magnusson [The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times. Computers and Operations Research 2005;32(4):727–47] develop a model for the single machine capacitated lot-sizing and scheduling problem (CLSP) with sequence dependent setup times and setup costs, incorporating all the usual features of setup carryovers. In this note we show that this model does not avoid disconnected subtours. A new set of constraints is added to the model to provide an exact formulation for this problem.     

A hybrid genetic algorithm for the single machine scheduling problem with sequence-dependent setup times

This paper presents a hybrid approach based on the integration between a genetic algorithm (GA) and concepts from constraint programming, multi-objective evolutionary algorithms and ant colony optimization for solving a scheduling problem. The main contributions are the integration of these concepts in a GA crossover operator. The proposed methodology is applied to a single machine scheduling problem with sequence-dependent setup times for the objective of minimizing the total tardiness. A sensitivity analysis of the hybrid approach is carried out to compare the performance of the GA and the hybrid genetic algorithm (HGA) approaches on different benchmarks from the literature. The numerical experiments demonstrate the HGA efficiency and effectiveness which generates solutions that approach those of the known reference sets and improves several lower bounds.     

Criteria selection and analysis for single machine dynamic on-line scheduling with multiple objectives and sequence-dependent setups

Fertile opportunities exist for research involving dynamic and stochastic scheduling with multiple conflicting objectives and sequence-dependent setups as little has been reported in the literature to date. This research focuses on understanding and identifying the criteria that could be combined into a single rule using the linear weighted aggregation approach to consider the contradicting needs of cycle time and delivery accuracy. Eight dispatching criteria are compared and evaluated using discrete event simulation. In most studies, the basic concept is to combine different dispatching criterion that performs the best in each objective into a single rule but this may be insufficient. Simulation results show that it is necessary to take into account not only the criterion’s strength in optimizing a performance objective but also the degree of trade-off it has on the other conflicting performance objectives of interest. A correlation analysis of the objectives used is also presented.     

The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times

We consider the single machine capacitated lot-sizing and scheduling problem (CLSP) with sequence-dependent setup costs and non-zero setup times, with the additional feature that setups may be carried over from one period to the next, and that setups are preserved over idle periods. We provide an exact formulation of this problem as a mixed-integer program.It is well known that the CLSP is NP-hard. Therefore, we have also developed a heuristic for solving large problem instances. This is coupled with a procedure for obtaining a lower bound on the optimal solution. We carry out a computational study to test the accuracy of several different lower bounding linear relaxations and the approximate solution obtained by the heuristic. In our study, the average deviation of the heuristic solution from the corresponding exact solution depends on the size of the problem and ranges from 10 to 16%. The heuristic is more effective when there are many more products than there are planning periods. This is a desirable property from a practical viewpoint since most firms are likely to implement such a procedure on a rolling horizon basis, solving the problem repeatedly for a few periods at a time.     

A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan

This paper considers the problem of scheduling a set of jobs subject to arbitrary release dates and sequence-dependent setup times on a single machine with the objective of minimizing the maximum completion of all the jobs, or makespan. This problem is often found in manufacturing processes such as painting and metalworking. A new mixed integer linear program (MILP) is firstly proposed. Because the problem is known to be NP-hard, a beam search heuristic is developed. Computational experiments are carried out using a well-known set of instances from the literature. Our results show that the proposed heuristic is effective in finding high quality solutions at low computational cost.     

Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—Variable neighborhood search approach

In scheduling problems, taking the sequence-dependent setup times into account is one of the important issues that have recently been considered by researchers in the production scheduling field. In this paper, we consider flexible job-shop scheduling problem (FJSP) with sequence-dependent setup times to minimize makespan and mean tardiness. The FJSP consists of two sub-problems from which the first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on all machines. To solve this problem, a variable neighborhood search (VNS) algorithm based on integrated approach is proposed. In the presented optimization method, the external loop controlled the stop condition of algorithm and the internal loop executed the search process. To search the solution space, the internal loop used two main search engines, i.e. shake and local search procedures. In addition, neighborhood structures related to the sequencing problem and the assignment problem were employed to generate neighboring solutions. To evaluate the performance of the proposed algorithm, 20 test problems in different sizes are randomly generated. Consequently, computational results and comparisons validate the quality of the proposed approach.     

Application of graph search and genetic algorithms for the single machine scheduling problem with sequence-dependent setup times and quadratic penalty function of completion times

In this paper, we consider the single machine scheduling problem with quadratic penalties and sequence-dependent (QPSD) setup times. QPSD is known to be NP-Hard. Only a few exact approaches, and to the best of our knowledge, no approximate approaches, have been reported in the literature so far. This paper discusses exact and approximate approaches for solving the problem, and presents empirical findings. We make use of a graph search algorithm, Memory-Based Depth-First Branch-and-Bound (MDFBB), and present an algorithm, QPSD_MDFBB that can optimally solve QPSD, and advances the state of the art for finding exact solutions. For finding approximate solutions to large problem instances, we make use of the idea of greedy stochastic search, and present a greedy stochastic algorithm, QPSD_GSA that provides moderately good solutions very rapidly even for large problems. The major contribution of the current paper is to apply QPSD_GSA to generate a subset of the starting solutions for a new genetic algorithm, QPSD_GEN, which is shown to provide near-optimal solutions very quickly. Owing to its polynomial running time, QPSD_GEN can be used for much larger instances than QPSD_MDFBB can handle. Experimental results have been provided to demonstrate the performances of these algorithms.     

Two-machine robotic cell scheduling problem with sequence-dependent setup times

In this paper, we introduce a new and practical two-machine robotic cell scheduling problem with sequence-dependent setup times (2RCSDST) along with different loading/unloading times for each part. Our objective is to simultaneously determine the sequence of robot moves and the sequence of parts that minimize the total cycle time. The proposed problem is proven to be strongly NP-hard. Using the Gilmore and Gomory (GnG) algorithm, a polynomial-time computable lower bound is provided.     

Artificial chromosomes with genetic algorithm 2 (ACGA2) for single machine scheduling problems with sequence-dependent setup times

Artificial chromosomes with genetic algorithm (ACGA) is one of the latest versions of the estimation of distribution algorithms (EDAs). This algorithm has already been applied successfully to solve different kinds of scheduling problems. However, due to the fact that its probabilistic model does not consider variable interactions, ACGA may not perform well in some scheduling problems, particularly if sequence-dependent setup times are considered. This is due to the fact that the previous job will influence the processing time of the next job. Simply capturing ordinal information from the parental distribution is not sufficient for a probabilistic model. As a result, this paper proposes a bi-variate probabilistic model to add into the ACGA. This new algorithm is called the ACGA2 and is used to solve single machine scheduling problems with sequence-dependent setup times in a common due-date environment. A theoretical analysis is given in this paper. Some heuristics and local search algorithm variable neighborhood search (VNS) are also employed in the ACGA2. The results indicate that the average error ratio of this ACGA2 is half the error ratio of the ACGA. In addition, when ACGA2 is applied in combination with other heuristic methods and VNS, the hybrid algorithm achieves optimal solution quality in comparison with other algorithms in the literature. Thus, the proposed algorithms are effective for solving the scheduling problems.     

A fuzzy-mixed-integer goal programming model for a parallel-machine scheduling problem with sequence-dependent setup times and release dates

This paper presents a new mixed-integer goal programming (MIGP) model for a parallel-machine scheduling problem with sequence-dependent setup times and release dates. Two objectives are considered in the model to minimize the total weighted flow time and the total weighted tardiness simultaneously. Due to the complexity of the above model and uncertainty involved in real-world scheduling problems, it is sometimes unrealistic or even impossible to acquire exact input data. Hence, we consider the parallel-machine scheduling problem with sequence-dependent set-up times under the hypothesis of fuzzy processing time's knowledge and two fuzzy objectives as the MIGP model. In addition, a quite effective and applicable methodology for solving the above fuzzy model are presented. At the end, the effectiveness of the proposed model and the denoted methodology is demonstrated through some test problems.     

A constructive heuristic for total flowtime minimization in a no-wait flowshop with sequence-dependent setup times

In this paper, we addressed the problem of scheduling jobs in a no-wait flow shop with sequence-dependent setup times with the objective of minimizing the total flow time. As this problem is well-known for being NP-hard, we present a new constructive heuristic, named QUARTS, in order to obtain good approximate solutions in a short CPU time. QUARTS breaks the problem in quartets in order to minimize the total flow time. The method was tested with other literature methods: BAH and BIH by Bianco et al. (1999) [6], TRIPS, by Brown et al. (2004) [7] and the metaheuristic Iterated Greedy with Local Search proposed by Ruiz and Stützle (2007) [25]. The computational results showed that IG_LS obtained the best results and QUARTS presented the best performance regarding other constructive heuristics.     

Minimizing total tardiness in a two-machine re-entrant flowshop with sequence-dependent setup times

We consider a two-machine re-entrant flowshop scheduling problem in which all jobs must be processed twice on each machine and there are sequence-dependent setup times on the second machine. For the problem with the objective of minimizing total tardiness, we develop dominance properties and a lower bound by extending those for a two-machine re-entrant flowshop problem (without sequence-dependent setup times) as well as heuristic algorithms, and present a branch and bound algorithm in which these dominance properties, lower bound, and heuristics are used. For evaluation of the performance of the branch and bound algorithm and heuristics, computational experiments are performed on randomly generated instances, and results are reported.     

Rolling-horizon and fix-and-relax heuristics for the parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs

In this paper we develop new rolling-horizon and fix-and-relax heuristics for the identical parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs. Unlike previous papers, our procedures are based on a compact formulation relying on the hypotheses of identical machines. This feature makes our approach suitable for large-scale applications (with hundreds of machines) arising in the textile and fiberglass industries. Moreover, our procedures are shown to provide a feasible solution for any feasible instance. Comparisons with lower bounds provided by a truncated branch-and-bound show that the gap between the best heuristic solution and the lower bound never exceeds 3%.     

Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints

This paper presents a novel, two-level mixed-integer programming model of scheduling N jobs on M parallel machines that minimizes bi-objectives, namely the number of tardy jobs and the total completion time of all the jobs. The proposed model considers unrelated parallel machines. The jobs have non-identical due dates and ready times, and there are some precedence relations between them. Furthermore, sequence-dependent setup times, which are included in the proposed model, may be different for each machine depending on their characteristics. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time using traditional approaches or optimization tools is extremely difficult. This paper proposes an efficient genetic algorithm (GA) to solve the bi-objective parallel machine scheduling problem. The performance of the presented model and the proposed GA is verified by a number of numerical experiments. The related results show the effectiveness of the proposed model and GA for small and large-sized problems.     

Minimizing worst-case regret of makespan on a single machine with uncertain processing and setup times

This research addresses a single machine scheduling problem with uncertain processing times and sequence-dependent setup times represented by intervals. Our objective is to obtain a robust schedule with the minimum absolute deviation from the optimal makespan in the worst-case scenario. The problem is reformulated as a robust traveling salesman problem (RTSP), whereby a property is utilized to efficiently identify worst-case scenarios. A local search-based heuristic that incorporates this property is proposed to solve the RTSP, along with a simulated annealing-based implementation. The effectiveness and efficiency of the proposed heuristic are compared to those of an exact solution method in the literature.     

A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times

This paper introduces and compares three different formulations of a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The setup is divided into two parts: one that can be performed at any time and another one that is restricted to be performed outside of a given time interval. As a result, the setup time between two jobs is a function of the completion time of the first job. The problem can be formulated as a time-dependent traveling salesman problem, where the travel time between two nodes is a function of the departure time from the first node. We show that the resulting formulation can be strengthened to provide better linear programming relaxation lower bounds. We also introduce several families of valid inequalities which are used within a branch-and-cut algorithm. Computational experiments show that this algorithm can solve some instances with up to 50 jobs within reasonable computing times.