An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem

In the no-idle flowshop, machines cannot be idle after finishing one job and before starting the next one. Therefore, start times of jobs must be delayed to guarantee this constraint. In practice machines show this behavior as it might be technically unfeasible or uneconomical to stop a machine in between jobs. This has important ramifications in the modern industry including fiber glass processing, foundries, production of integrated circuits and the steel making industry, among others. However, to assume that all machines in the shop have this no-idle constraint is not realistic. To the best of our knowledge, this is the first paper to study the mixed no-idle extension where only some machines have the no-idle constraint. We present a mixed integer programming model for this new problem and the equations to calculate the makespan. We also propose a set of formulas to accelerate the calculation of insertions that is used both in heuristics as well as in the local search procedures. An effective iterated greedy (IG) algorithm is proposed. We use an NEH-based heuristic to construct a high quality initial solution. A local search using the proposed accelerations is employed to emphasize intensification and exploration in the IG. A new destruction and construction procedure is also shown. To evaluate the proposed algorithm, we present several adaptations of other well-known and recent metaheuristics for the problem and conduct a comprehensive set of computational and statistical experiments with a total of 1750 instances. The results show that the proposed IG algorithm outperforms existing methods in the no-idle and in the mixed no-idle scenarios by a significant margin.     

A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation

The hybrid flowshop scheduling (HFS) problem with the objective of minimising the makespan has important applications in a variety of industrial systems. This paper presents an effective discrete artificial bee colony (DABC) algorithm that has a hybrid representation and a combination of forward decoding and backward decoding methods for solving the problem. Based on the dispatching rules, the well-known NEH heuristic, and the two decoding methods, we first provide a total of 24 heuristics. Next, an initial population is generated with a high level of quality and diversity based on the presented heuristics. A new control parameter is introduced to conduct the search of employed bees and onlooker bees with the intention of balancing the global exploration and local exploitation, and an enhanced strategy is proposed for the scout bee phase to prevent the algorithm from searching in poor regions of the solution space. A problem-specific local refinement procedure is developed to search for solution space that is unexplored by the honey bees. Afterward, the parameters and operators of the proposed DABC are calibrated by means of a design of experiments approach. Finally, a comparative evaluation is conducted, with the best performing algorithms presented for the HFS problem under consideration, and with adaptations of some state-of-the-art metaheuristics that were originally designed for other HFS problems. The results show that the proposed DABC performs much better than the other algorithms in solving the HFS problem with the makespan criterion.     

An estimation of distribution algorithm for lot-streaming flow shop problems with setup times

Lot-streaming flow shops have important applications in different industries including textile, plastic, chemical, semiconductor and many others. This paper considers an n-job m-machine lot-streaming flow shop scheduling problem with sequence-dependent setup times under both the idling and no-idling production cases. The objective is to minimize the maximum completion time or makespan. To solve this important practical problem, a novel estimation of distribution algorithm (EDA) is proposed with a job permutation based representation. In the proposed EDA, an efficient initialization scheme based on the NEH heuristic is presented to construct an initial population with a certain level of quality and diversity. An estimation of a probabilistic model is constructed to direct the algorithm search towards good solutions by taking into account both job permutation and similar blocks of jobs. A simple but effective local search is added to enhance the intensification capability. A diversity controlling mechanism is applied to maintain the diversity of the population. In addition, a speed-up method is presented to reduce the computational effort needed for the local search technique and the NEH-based heuristics. A comparative evaluation is carried out with the best performing algorithms from the literature. The results show that the proposed EDA is very effective in comparison after comprehensive computational and statistical analyses.     

A multiobjective genetic algorithm for job shop scheduling

In this paper, a Multi Objective Genetic Algorithm (MOGA) is proposed to derive the optimal machine-wise priority dispatching rules ( pdrs ) to resolve the conflict among the contending jobs in the Giffler and Thompson (GT) procedure applied for job shop problems. The performance criterion considered is the weighed sum of the multiple objectives minimization of makespan, minimization of total idle time of machines and minimization of total tardiness. The weights assigned for combining the objectives into a scalar fitness function are not constant. They are specified randomly for each evaluation. This in turn leads to the multidirectional search in the proposed MOGA, which in turn mitigates the solution being entrapped in local minima. The applicability and usefulness of the proposed methodology for the scheduling of job shops is illustrated with 28 benchmark problems available in the open literature.     

A simulated annealing algorithm for job shop scheduling

In this paper, the job shop scheduling problem is considered with the objective of minimization of makespan time. We first reviewed the literature on job shop scheduling using meta-heuristics. Then a simulated annealing algorithm is presented for scheduling in a job shop. To create neighbourhoods, three perturbation schemes, viz. pairwise exchange, insertion, and random insertion are used, and the effect of them on the final schedule is also compared. The proposed simulated annealing algorithm is compared with existing genetic algorithms and the comparative results are presented. For comparative evaluation, a wide variety of data sets are used. The proposed algorithm is found to perform well for scheduling in the job shop.     

Flow shop scheduling by transportation model

This paper describes the classical problem of scheduling n jobs on m machines in a flow shop. A schedule evaluation algorithm is presented, which for job-pairs, generates a schedule evaluation matrix. The matrix is the input data to a transportation problem, the solution of which gives near-optimal jobsequence and makespan. The performance of the algorithm is discussed.     

The permutation flow shop problem with blocking. A tabu search approach

This paper develops a fast tabu search algorithm to minimize makespan in a flow shop problem with blocking. Some properties of the problem associated with the blocks of jobs have been presented and discussed. These properties allow us to propose a specific neighbourhood of algorithms. Also, the multimoves are used that consist in performing several moves simultaneously in a single iteration and guide the search process to more promising areas of the solutions space, where good solutions can be found. It allow us to accelerate the convergence of the algorithm. Besides, a dynamic tabu list is proposed that assists additionally to avoid being trapped at a local optimum. The proposed algorithms are empirically evaluated and found to be relatively more effective in finding better solutions than attained by the leading approaches in a much shorter time. The presented ideas can be applied in many local search procedures.     

Simulated annealing procedure for scheduling competing tasks in flexible manufacturing

This paper presents a simulated annealing SA procedure heuristic for the problem of scheduling N tasks on a machine equipped with an automatic tool changer to minimize the makespan time. The problem is first formulated as a symmetric travelling salesman problem TSP . A local search heuristic procedure is developed, then embedded into SA algorithm to enhance its performance. The implemented SA heuristic has the following features: an exponential acceptance function with non-monotonic cooling schedule, heuristic pre-processing, and a neighbourhood of changing the sequence of a small number of tasks and named the k-interchange procedure. The algorithm is compared with an exact solution method on a set of practical-sized problems. The proposed algorithm performed very well in terms of solution quality and computation time.     

The no-wait job shop with regular objective: a method based on optimal job insertion

The no-wait job shop problem (NWJS-R) considered here is a version of the job shop scheduling problem where, for any two operations of a job, a fixed time lag between their starting times is prescribed. Also, sequence-dependent set-up times between consecutive operations on a machine can be present. The problem consists in finding a schedule that minimizes a general regular objective function. We study the so-called optimal job insertion problem in the NWJS-R and prove that this problem is solvable in polynomial time by a very efficient algorithm, generalizing a result we obtained in the case of a makespan objective. We then propose a large neighborhood local search method for the NWJS-R based on the optimal job insertion algorithm and present extensive numerical results that compare favorably with current benchmarks when available.     

An asymptotically optimal algorithm for large-scale mixed job shop scheduling to minimize the makespan

This paper considers the large-scale mixed job shop scheduling problem with general number of jobs on each route. The problem includes ordinary machines, batch machines (with bounded or unbounded capacity), parallel machines, and machines with breakdowns. The objective is to find a schedule to minimize the makespan. For the problem, we define a virtual problem and a corresponding virtual schedule, based on which our algorithm TVSA is proposed. The performance analysis of the algorithm shows the gap between the obtained solution and the optimal solution is O(1), which indicates the algorithm is asymptotically optimal.     

A mathematical model for job shop scheduling with multiple process plan consideration per job

In this paper, a mixed integer programming model is formulated for scheduling a set of jobs through a shop when each job is supplied or provided with multiple process plans or process routings. Simultaneous selection of a process plan for each job and the sequencing of the jobs through the machines in the shop based on the set of selected process plans is addressed. The procedure developed seeks to integrate the selection of machines for each job and the sequencing of jobs on each machine based on the objective of minimizing production makespan. the application of the procedure is demonstrated with an example problem. The following conclusions were drawn as a result of the research: (1) the procedure developed produces optimal or near optimal solution; (2) the benefit from the developed approach is that it allows a shop to adaptively select process plans for jobs to optimize on production makespan. By combining solution quality with scheduling flexibility and efficiency, the productivity of a shop can be greatly enhanced.     

Designing a tabu search algorithm for the two-stage flow shop problem with secondary criterion

This paper discusses the process of desigining a tabu search-based heuristic for the two-stage flow shop problem with makespan minimization as the primary criterion and the minimization of total flow time as the secondary criterion. A factorial experiment is designed to analyse thoroughly the effects of four different factors, i.e. the initial solution, type of move, size of neighbourhood and the list size, on the performance of the tabu search-based heuristic. Using the techniques of evolution curves, and response tables and response graphs, coupled with the Taguchi method, the best combination of the factors for the tabu search-based heuristic is identified, and the effectiveness of the heuristic algorithm in finding an optimal solution is evaluated by comparing its performance with the best known heuristic to solve this problem.     

Decomposition algorithms for the integrated process planning and scheduling problem

There are several algorithms to solve the integrated process planning and scheduling (IPPS) problem (i.e., flexible job shop scheduling with process plan flexibility) in the literature. All the existing algorithms for IPPS are heuristic-based search methods and no research has investigated the use of exact solution methods for this problem. We develop several decomposition approaches based on the logic-based Benders decomposition (LBBD) algorithm. Our LBBD algorithm allows us to partition the decision variables in the IPPS problem into two models, master-problem and sub-problem. The master-problem determines process plan and operation-machine assignment, while the sub-problem optimizes sequencing and scheduling decisions. To achieve faster convergence, we develop two relaxations for the optimal makespan objective function and incorporate them into the master-problem. We analyze the performance and further enhance the algorithm with two ideas, a Benders optimality cut based on the critical path and a faster heuristic way to solve the sub-problem. 16 standard benchmark instances available in the literature are solved to evaluate and compare the performances of our algorithms with those of the state-of-the-art methods in the literature. The proposed algorithm either results in the optimal solution or improves the best-known solutions in all the existing instances, demonstrating its superiority to the existing state-of-the-art methods in literature.     

Energy-oriented bi-objective optimization for the tempered glass scheduling

This paper investigates a real life bi-objective hybrid flow shop scheduling problem in an energy-intensive manufacturing system, in which glass is produced successively in cutting, printing and tempering stages. The problem aims to simultaneously optimize makespan and the total electricity cost under a time-of-use electricity pricing policy. The glass production has to respect the following environments: (i) the cutting and printing operations are processed in parallel machine environments; (ii) the tempering operation is processed on a batch machine; (iii) machine eligibility and setup time have to be considered in the cutting and printing stages; (iv) the whole manufacturing system is under a time-of-use electricity pricing policy. For the problem, an integer programming model is firstly proposed and shown to be strongly NP-hard. Then a model-based heuristic is adopted and a bi-objective differential evolution algorithm (BODE) is devised based on problem features. Computational experiments on randomly generated instances demonstrated that the BODE outperforms the model-based heuristic in terms of computation time and solution quality. Moreover, with mild increase on computation burden, the BODE significantly outperforms the classic NSGA II in terms of solution quality.     

一种求解双目标flow shop排序问题的进化算法

提出一种求解双目标flow shop排序的递进多目标进化算法.算法采用改进的精英复制策略,在实现精英保留的前提下降低了计算复杂性;通过递进进化模式增加群体多样性,改善了算法收敛性;通过群体进化过程中对非劣解集进行竞争型可变邻域启发式搜索,增强了算法局部搜索性能.采用新算法和参照算法NSGA-II对31个标准双目标flow shop算例进行优化.研究结果表明,新算法在所有算例的求解中均获得了优于NSGA-II的非劣解集,验证了算法的有效性.     

Energy-efficient no-wait permutation flow shop scheduling by adaptive multi-objective variable neighborhood search

This paper considers an energy-efficient no-wait permutation flow shop scheduling problem to minimize makespan and total energy consumption, simultaneously. The processing speeds of machines can be dynamically adjusted for different jobs. In general, lower processing speeds require less energy consumption but result in longer processing times, while higher speeds take the opposite effect. To reach the Pareto front of the problem, we propose an adaptive multi-objective variable neighborhood search (AM-VNS) algorithm. Specifically, we first design two basic speed adjusting heuristics which can reduce the energy consumption of a given solution without worsening its makespan. Two widely used neighborhood-generating operations, i.e., insertion and swap, are adapted and integrated into the variable neighborhood descent phase. With respect to their executing order, two variable neighborhood descent structures can be designed. We adopt an adaptive mechanism to dynamically determine which structure will be selected to handle the current solution. To further improve the performance of the algorithm, we develop a novel problem-specific shake procedure. We also introduce accelerating techniques to speed up the algorithm. Computational results show that the AM-VNS algorithm outperforms multi-objective evolutionary algorithms NSGA-II and SPEA-II.     

The blocking job shop with rail-bound transportation

The blocking job shop with rail-bound transportation (BJS-RT) considered here is a version of the job shop scheduling problem characterized by the absence of buffers and the use of a rail-bound transportation system. The jobs are processed on machines and are transported from one machine to the next by mobile devices (called robots) that move on a single rail. The robots cannot pass each other, must maintain a minimum distance from each other, but can also “move out of the way”. The objective of the BJS-RT is to determine for each machining operation its starting time and for each transport operation its assigned robot and starting time, as well as the trajectory of each robot, in order to minimize the makespan. Building on previous work of the authors on the flexible blocking job shop and an analysis of the feasible trajectory problem, a formulation of the BJS-RT in a disjunctive graph is derived. Based on the framework of job insertion in this graph, a local search heuristic generating consistently feasible neighbor solutions is proposed. Computational results are presented, supporting the value of the approach.     

O(m2) ALGORITHMS FOR THE TWO AND THREE SUBLOT LOT STREAMING PROBLEM

Lot streaming is the process of splitting a job or lot into sublots to reduce its makespan on a sequence of machines. The goal in the lot streaming problem is to find the optimal size of each sublot that will minimize the makespan. The makespan is defined as the time the last sublot completes its processing on the last machine. If the sizes of these sublots are restricted to remain the same on all machines, the solution is called a consistent sublot solution. However, if the sizes of the sublots are allowed to vary, the solution is referred to as a nonconsistent or variable sublot solution. Also, if the machines must be in operation continuously from the first to the last sublot, the solution is a no idling solution. When setups are explicitly considered in the problem, there will be two cases. If setups on each machine require some portion of the first sublot be present by the machine, the problem is referred to as the attached setup time problem. If setups can be performed ahead of time before the first sublot reaches the particular machine, the corresponding problem is referred to as the detached setup problem. Finally, if the machines are allowed to be idle between the processing of sublots, the resultant solution is an intermittent idling solution. In this paper, the consistent sublot lot streaming problem with intermittent idling and no setups is discussed. The models developed also assume that the number of sublots are fixed and known. The m machine two sublot lot streaming problem is reviewed. An algorithm for the three sublot, m machine problem is derived using a network representation of the problem. The complexity of the algorithm is O (m²). Finally, using the insights from three sublot problem, a heuristic algorithm is provided for the m machine, n sublot problems. The results on the proposed heuristic are very encouraging; average percent deviation from optimal makespan is approximately at 0.76% on 155 randomly generated problems with different m and n values.     

The permutation flow shop problem with just in time production considerations

This research presents a variation to the permutation flow shop problem where Just In Time (JIT) production requirements are taken into account. The model developed in this research employs dual objectives. In addition to the traditional objective of minimizing the production makespan, minimization of Miltenburg's material usage rate is also incorporated. In this model, multiple units of any product are permitted in the production sequence. However, the minimization of material usage rates attempts to prevent batch scheduling of products and allows unit flow of products as required in demand flow manufacturing. A solution method is proposed for determining an optimal production sequence via an efficient frontier approach and Simulated Annealing (SA). Test problems and specific performance criteria are used to assess the solutions generated by the proposed method. Experimental results presented in this paper show that the use of the efficient frontier and SA provide solutions that approach the optimal solution for the performance measures used in this research.     

Asymptotically optimal policy for stochastic job shop scheduling problem to minimize makespan

This paper studies the large-scale stochastic job shop scheduling problem with general number of similar jobs, where the processing times of the same step are independently drawn from a known probability distribution, and the objective is to minimize the makespan. For the stochastic problem, we introduce the fluid relaxation of its deterministic counterpart, and define a fluid schedule for the fluid relaxation. By tracking the fluid schedule, a policy is proposed for the stochastic job shop scheduling problem. The expected value of the gap between the solution produced by the policy and the optimal solution is proved to be O(1), which indicates the policy is asymptotically optimal in expectation.