Integrating non-preemptive open shops scheduling with sequence-dependent setup times using advanced metaheuristics

In this article, we consider non-preemptive open shops scheduling problem (OSSP) where setup times are sequence-dependent (SDST) on each machine to minimize makespan. The contributions of this article are threefold. Firstly, we incorporate a very practical assumption in our problem, SDST, which, according to Allahverdi et al. (2008) [Allahverdi, A., Ng, C. T., Cheung, T. C. E., & Kovalyov, Y. M. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187(3), 985–1032], no paper has ever attempted to integrate into OSSP. Secondly, we propose two new advanced metaheuristics: multi-neighborhood search simulated annealing and hybrid simulated annealing to tackle the problem at hand. Thirdly, for the first time, we adapt two well-known constructive heuristics: longest total processing time and longest total remaining processing from the literature so as to consider the case of SDSTs. We also apply genetic algorithm from the literature of OSSP to embrace the concepts of SDST. Since there is no standard SDST-OSSP benchmark, we make certain adaptations on the Taillard’s benchmark [Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 278–285] to include setup times. An experimental design based on foregoing benchmark is conducted to evaluate the competitiveness and robustness of our proposed algorithm against some effective algorithms in the literature. The obtained results strongly support the high performance of our proposed algorithms with respect to other well-known heuristic and metaheuristic algorithms.     

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.     

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.     

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.     

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.     

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.     

Hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints

One of the common assumptions in the field of scheduling is that machines are always available in the planning horizon. This may not be true in realistic problems since machines might be busy processing some jobs left from previous production horizon, breakdowns or preventive maintenance activities. Another common assumption is the consideration of setup times as a part of processing times, while in some industries, such as printed circuit board and automobile manufacturing, not only setups are an important factor but also setup magnitude of a job depends on its immediately preceding job on the same machine, known as sequence-dependent setup times. In this paper, we consider hybrid flexible flowshops with sequence-dependent setup times and machine availability constraints caused by preventive maintenance. The optimization criterion is the minimization of makespan. Since this problem is NP-hard in the strong sense, we propose three heuristics, based on SPT, LPT and Johnson rule and two metaheuristics based on genetic algorithm and simulated annealing. Computational experiments are performed to evaluate the efficiencies of the algorithms.     

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 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.     

Scheduling flowshops with finite buffers and sequence-dependent setup times

In this paper we explore flowshop scheduling problems containing both sequence-dependent setup times and finite buffers. To the best of our knowledge, problems containing both of these complexities have not been addressed previously in the literature. The problem is clearly NP-hard and therefore we only consider heuristic solution methods. We propose a tabu search based solution procedure. Computational results demonstrate the effectiveness of this approach relative to the other methods discussed.     

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.     

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.     

A two-stage heuristic for single machine capacitated lot-sizing and scheduling with sequence-dependent setup costs

This paper considers a single machine capacitated lot-sizing and scheduling problem. The problem is to determine the lot sizes and the sequence of lots while satisfying the demand requirements and the machine capacity in each period of a planning horizon. In particular, we consider sequence-dependent setup costs that depend on the type of the lot just completed and on the lot to be processed. The setup state preservation, i.e., the setup state at the end of a period is carried over to the next period, is also considered. The objective is to minimize the sum of setup and inventory holding costs over the planning horizon. Due to the complexity of the problem, we suggest a two-stage heuristic in which an initial solution is obtained and then it is improved using a backward and forward improvement method that incorporates various priority rules to select the items to be moved. Computational tests were done on randomly generated test instances and the results show that the two-stage heuristic outperforms the best existing algorithm significantly. Also, the heuristics with better priority rule combinations were used to solve case instances and much improvement is reported over the conventional method as well as the best existing algorithm.     

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.     

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.     

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.     

ABC-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times

To date, the topic of unrelated parallel machine scheduling problems with machine-dependent and job sequence-dependent setup times has received relatively little research attention. In this study, a hybrid artificial bee colony (HABC) algorithm is presented to solve this problem with the objective of minimizing the makespan. The performance of the proposed HABC algorithm was evaluated by comparing its solutions to state-of-the-art metaheuristic algorithms and a high performing artificial bee colony (ABC)-based algorithm. Extensive computational results indicate that the proposed HABC algorithm significantly outperforms these best-so-far algorithms. Since the problem addressed in this study is a core topic for numerous industrial applications, this article may help to reduce the gap between theoretical progress and industrial practice.     

Lot-sizing scheduling with batch setup times

This paper is concerned with scheduling independent jobs on m parallel machines in such a way that the makespan is minimized. Each job j is allowed to split arbitrarily into several parts, which can be individually processed on any machine at any time. However, a setup for uninterrupted s_j time units is required before any split part of job j can be processed on any machine. The problem is strongly NP-hard if the number m of machines is variable and weakly NP-hard otherwise. We give a polynomial-time -approximation algorithm for the former case and a fully polynomial-time approximation scheme for the latter. AMS Subject Classifications: 68M20 · 90B35 · 90C59     

Evaluation of multi-product lean manufacturing systems with setup and erratic demand

The consideration of demand variability in Multi-Product Lean Manufacturing Environment (MPLME) is an innovation in production system engineering. Manufacturing systems that fail to recognise demand variability generate high Work-In-Process (WIP) and low throughput in MPLME. In response to demand variability, organisations allocate large quantities of Production Authorisation Cards (PAC). A large proportion of PAC results in a high WIP level. However, the Shared Kanban Allocation Policy (S-KAP) allows the distribution of PAC among part-types, which minimises WIP in MPLME. Nevertheless, some existing lean manufacturing control strategies referred as Pull Production Control Strategies (PPCS) that have shown improved performance in single-product systems failed to operate S-KAP. The recently developed Basestock–Kanban-CONWIP (BK-CONWIP) strategy has the capability of minimising WIP while maintaining low backlog and volume flexibility. This paper investigates the effects of erratic demand on the performance of PPCS in MPLME. It is shown that S-KAP BK-CONWIP outperforms other PPCS. Finally, it is feasible to design quick-response PPCS for MPLME under erratic demand.     

Minimization of maximum lateness on parallel machines with sequence-dependent setup times and job release dates

In this paper, we consider an identical parallel machine scheduling problem with sequence-dependent setup times and job release dates. An improved iterated greedy heuristic with a sinking temperature is presented to minimize the maximum lateness. To verify the developed heuristic, computational experiments are conducted on a well-known benchmark problem data set. The experimental results show that the proposed heuristic outperforms the basic iterated greedy heuristic and the state-of-art algorithms on the same benchmark problem data set. It is believed that this improved approach will also be helpful for other applications.