A neighborhood for complex job shop scheduling problems with regular objectives

Due to the limited applicability in practice of the classical job shop scheduling problem, many researchers have addressed more complex versions of this problem by including additional process features, such as time lags, setup times, and buffer limitations, and have pursued objectives that are more practically relevant than the makespan, such as total flow time and total weighted tardiness. However, most proposed solution approaches are tailored to the specific scheduling problem studied and are not applicable to more general settings. This article proposes a neighborhood that can be applied for a large class of job shop scheduling problems with regular objectives. Feasible neighbor solutions are generated by extracting a job from a given solution and reinserting it into a neighbor position. This neighbor generation in a sense extends the simple swapping of critical arcs, a mechanism that is widely used in the classical job shop but that is not applicable in more complex job shop problems. The neighborhood is embedded in a tabu search, and its performance is evaluated with an extensive experimental study using three standard job shop scheduling problems: the (classical) job shop, the job shop with sequence-dependent setup times, and the blocking job shop, combined with the following five regular objectives: makespan, total flow time, total squared flow time, total tardiness, and total weighted tardiness. The obtained results support the validity of the approach.     

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.     

Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times

In this paper, we discuss a scheduling problem for jobs on identical parallel machines. Ready times of the jobs, precedence constraints, and sequence-dependent setup times are considered. We are interested in minimizing the performance measure total weighted tardiness that is important for achieving good on-time delivery performance. Scheduling problems of this type appear as subproblems in decomposition approaches for large scale job shops with automated transport of the jobs as, for example, in semiconductor manufacturing. We suggest several variants of variable neighborhood search (VNS) schemes for this scheduling problem and compare their performance with the performance of a list based scheduling approach based on the Apparent Tardiness Cost with Setups and Ready Times (ATCSR) dispatching rule. Based on extensive computational experiments with randomly generated test instances we are able to show that the VNS approach clearly outperforms heuristics based on the ATCSR dispatching rule in many situations with respect to solution quality. When using the schedule obtained by ATCSR as an initial solution for VNS, then the entire scheme is also fast and can be used as a subproblem solution procedure for complex job shop decomposition approaches.     

Tabu search and lower bound for an industrial complex shop scheduling problem

This paper deals with an industrial shop scheduling problem that arises in a metal goods production group. The scheduling problem can be seen as a multi-mode job shop with assembly. Jobs have additional constraints such as release date, due date and sequence-dependent setup times. The aim of the decision-makers is to minimize the maximum lateness. This article introduces a tabu search procedure to solve the whole problem and a valid lower bound used to evaluate the tabu search procedure.     

Family scheduling with batch availability in flow shops to minimize makespan

This paper addresses a batch scheduling problem in flow shop production systems, where job families are formed based on setup similarities. In order to improve setup efficiency, we consider batching decisions in our solution procedure. Due to its high practical relevance, the batch availability assumption is also adopted in this study. In the presence of sequence-dependent setup times, it is proved that a permutation flow shop is generally not optimal. Therefore, our objective is to determine solutions with inconsistent batches, which essentially lead to non-permutation schedules, to minimize makespan. After examining structural properties, we develop a tabu search algorithm with multiple neighbourhood functions. Computational results confirm the remarkable benefits of batching decisions. Our algorithm also outperforms some well-known and well-performing approaches.     

Enhancing genetic algorithms for dependent job scheduling in grid computing environments

Genetic Algorithms (GAs) are stochastic search techniques based on principles of natural selection and recombination that attempt to find optimal solutions in polynomial time by manipulating a population of candidate solutions. GAs have been widely used for job scheduling optimisation in both homogeneous and heterogeneous computing environments. When compared with list scheduling heuristics, GAs can potentially provide better solutions but require much longer processing time and significant experimentation to determine GA parameters. This paper presents a GA for scheduling dependent jobs in grid computing environments. A?number of selection and pre-selection criteria for the GA are evaluated with an aim to improve GA performance in job scheduling optimization. A?Task Matching with Data scheme is proposed as a GA mutation operator. Furthermore, the effect of the choice of heuristics for seeding the GA is investigated.     

Two-machine flow shop scheduling integrated with preventive maintenance planning

This paper investigates an integrated optimisation problem of production scheduling and preventive maintenance (PM) in a two-machine flow shop with time to failure of each machine subject to a Weibull probability distribution. The objective is to find the optimal job sequence and the optimal PM decisions before each job such that the expected makespan is minimised. To investigate the value of integrated scheduling solution, computational experiments on small-scale problems with different configurations are conducted with total enumeration method, and the results are compared with those of scheduling without maintenance but with machine degradation, and individual job scheduling combined with independent PM planning. Then, for large-scale problems, four genetic algorithm (GA) based heuristics are proposed. The numerical results with several large problem sizes and different configurations indicate the potential benefits of integrated scheduling solution and the results also show that proposed GA-based heuristics are efficient for the integrated problem.     

An interactive micro-computer software for general three machines flow shop sequencing problems

The order in which jobs pass through machines or work centres is a sequencing problem. The sequencing problems occur in flow shop as well as job shop production systems. In flow shop production systems, each job follows the same processing route whereas in the job shop production system, jobs flow across machines or work stations on many different routes. For optimizing the sequencing of such jobs, production planners may adopt different criteria such as makespan time, average completion time, due date performance, machine utilization and so forth. In the absence of given criteria, it is usual to accept the makespan time as the criteria and to attempt to minimize this. In a 2-machines flow shop, the jobs can be sequenced optimally for minimum total makespan time by using Johnson's algorithm [1]. Johnson's algorithm can also be used to find the optimal sequence for special three-machines flow shop problems satisfying certain conditions [1]. But for general three-machines sequencing problems, optimal sequence based on makespan time can be obtained by using a branch and bound solution procedure [1].

In this paper, the branch-and-bound procedure have been used to develop an interactive program in BASIC for finding the optimal job sequence for general three-machines flow shop problems. This program which is written for an IBM-PC or IBM-PC compatibles, also provides the time chart and the time chart drawing. Furthermore, it gives the results of the branching steps (i.e the partial sequences) in a tabular form.     

A tabu search heuristic for a sequence-dependent and time-dependent scheduling problem on a single machine

This paper introduces a tabu search heuristic for a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The problem consists in scheduling a set of dependent jobs, where the transition between two jobs comprises an unrestricted setup that can be performed at any time, and a restricted setup that must be performed outside of a given time interval which repeats daily in the same position. The setup time between two jobs is thus a function of the completion time of the first job. The tabu search heuristic relies on shift and swap moves, and a surrogate objective function is used to speed-up the neighborhood evaluation. Computational experiments show that the proposed heuristic consistently finds better solutions in less computation time than a recent branch-and-cut algorithm. Furthermore, on instances where the branch-and-cut algorithm cannot find the optimal solution, the heuristic always identifies a better solution.     

Evolutionary algorithms for scheduling m-machine flow shop with lot streaming

This paper addresses the problem of making sequencing and scheduling decisions for n jobs–m-machines flow shops under lot sizing environment. Lot streaming (Lot sizing) is the process of creating sub lots to move the completed portion of a production sub lots to down stream machines. There is a scope for efficient algorithms for scheduling problems in m-machine flow shop with lot streaming. In recent years, much attention is given to heuristics and search techniques. Evolutionary algorithms that belong to search heuristics find more applications in recent research. Genetic algorithm (GA) and hybrid genetic algorithm (HEA) also known as hybrid evolutionary algorithm fall under evolutionary heuristics. On this concern this paper proposes two evolutionary algorithms namely, GA and HEA to evolve best sequence for makespan/total flow time criterion for m-machine flow shop involved with lot streaming and set-up time. The following two algorithms are used to evaluate the performance of the proposed GA and HEA: (i) Baker's algorithm (BA), an optimal solution procedure for two-machine flow shop problem with lot streaming and makespan objective criterion and (ii) simulated annealing algorithm (SA) for m-machine flow shop problem with lot streaming and makespan and total flow time criteria.     

A distributed shifting bottleneck heuristic for complex job shops

In this paper, we consider distributed versions of a modified shifting bottleneck heuristic for complex job shops. The considered job shop environment contains parallel batching machines, machines with sequence-dependent setup times and reentrant process flows. Semiconductor wafer fabrication facilities are typical examples for manufacturing systems with these characteristics. The used performance measure is total weighted tardiness (TWT). We suggest a two-layer hierarchical approach in order to decompose the overall scheduling problem. The upper (or top) layer works on an aggregated model. Based on appropriately aggregated routes it determines start dates and planned due dates for the jobs within each single work area, where a work area is defined as a set of parallel machine groups. The lower (or base) layer uses the start dates and planned due dates in order to apply shifting bottleneck heuristic type solution approaches for the jobs in each single work area. We conduct simulation experiments in a dynamic job shop environment in order to assess the performance of the heuristic. It turns out that the suggested approach outperforms a pure First In First Out (FIFO) dispatching scheme and provides a similar solution quality as the original modified shifting bottleneck heuristic.     

基于遗传算法的滚动调度策略*

本文研究了动态加工环境下的一类Ｊｏｂ－Ｓｈｏｐ调度问题，提出了一种基于遗传算法的滚动调度策略，其要点是：１）借鉴预测控制的思想，采用ｔｉｍｅ－ｂａｓｅｄ和ｊｏｂ－ｂａｓｅｄ的滚动调度策略适应动态环境和要求的多变性。２）以遗传算法和分派规则相结合，处理考虑与操作序列有关的工件安装时间和工件到期时间约束的复杂调度问题。文中给出了在工件到期时间发生改变的动态环境中两种滚动调度算法的调度结果，并与静态调度     

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.     

Greedy randomized adaptive search for dynamic flexible job-shop scheduling

Dynamic flexible job shop scheduling problem is studied under the events such as new order arrivals, changes in due dates, machine breakdowns, order cancellations, and appearance of urgent orders. This paper presents a constructive algorithm which can solve FJSP and DFJSP with machine capacity constraints and sequence-dependent setup times, and employs greedy randomized adaptive search procedure (GRASP). Besides, Order Review Release (ORR) mechanism and order acceptance/rejection decisions are also incorporated into the proposed method in order to adjust capacity execution considering customer due date requirements. The lexicographic method is utilized to assess the objectives: schedule instability, makespan, mean tardiness and mean flow time. A group of experiments is also carried out in order to verify the suitability of the GRASP in solving the flexible job shop scheduling problem. Benchmark problems are formed for different problem scales with dynamic events. The event-driven rescheduling strategy is also compared with periodical rescheduling strategy. Results of the extensive computational experiment presents that proposed approach is very effective and can provide reasonable schedules under event-driven and periodic scheduling scenarios.     

A simulated annealing algorithm approach to hybrid flow shop scheduling with sequence-dependent setup times

One of the scheduling problems with various applications in industries is hybrid flow shop. In hybrid flow shop, a series of n jobs are processed at a series of g workshops with several parallel machines in each workshop. To simplify the model construction in most research on hybrid flow shop scheduling problems, the setup times of operations have been ignored, combined with their corresponding processing times, or considered non sequence-dependent. However, in most real industries such as chemical, textile, metallurgical, printed circuit board, and automobile manufacturing, hybrid flow shop problems have sequence-dependent setup times (SDST). In this research, the problem of SDST hybrid flow shop scheduling with parallel identical machines to minimize the makespan is studied. A novel simulated annealing (NSA) algorithm is developed to produce a reasonable manufacturing schedule within an acceptable computational time. In this study, the proposed NSA uses a well combination of two moving operators for generating new solutions. The obtained results are compared with those computed by Random Key Genetic Algorithm (RKGA) and Immune Algorithm (IA) which are proposed previously. The results show that NSA outperforms both RKGA and IA.     

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.     

Using genetic algorithms in process planning for job shop machining

This paper presents a novel computer-aided process planning model for machined parts to be made in a job shop manufacturing environment. The approach deals with process planning problems in a concurrent manner in generating the entire solution space by considering the multiple decision-making activities, i.e., operation selection, machine selection, setup selection, cutting tool selection, and operations sequencing, simultaneously. Genetic algorithms (GAs) were selected due to their flexible representation scheme. The developed GA is able to achieve a near-optimal process plan through specially designed crossover and mutation operators. Flexible criteria are provided for plan evaluation. This technique was implemented and its performance is illustrated in a case study. A space search method is used for comparison     

Genetic algorithm-based heuristics for an open shop scheduling problem with setup,processing, and removal times separated

This report proposes a solution to the open shop scheduling problem with the objective of minimizing total job tardiness in the system. Some practical processing restrictions, such as independent setup and dependent removal times, are taken into account as well. The addressed problem is first described as a 0–1 integer programming model, and is then solved optimally. Subsequently, some hybrid genetic-based heuristics are proposed to solve the problem in an acceptable computation time. To demonstrate the adaptability of these heuristics, some performance comparisons are made with solutions provided by running either a mathematical programming model or certain classic meta-heuristics such as genetic algorithm, simulated annealing, and tabu search in various manufacturing scenarios. The experimental results show that the hybrid genetic-based heuristics perform well, especially the DGA. However, these heuristics require some more additional computations but are still acceptable.     

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