New high performing heuristics for minimizing makespan in permutation flowshops

The well-known NEH heuristic from Nawaz, Enscore and Ham proposed in 1983 has been recognized as the highest performing method for the permutation flowshop scheduling problem under the makespan minimization criterion. This performance lead is maintained even today when compared against contemporary and more complex heuristics as shown in recent studies. In this paper we show five new methods that outperform NEH as supported by careful statistical analyses using the well-known instances of Taillard. The proposed methods try to counter the excessive greediness of NEH by carrying out re-insertions of already inserted jobs at some points in the construction of the solution. The five proposed heuristics range from extensions that are slightly slower than NEH in most tested instances to more comprehensive methods based on local search that yield excellent results at the expense of some added computational time. Additionally, NEH has been profusely used in the flowshop scheduling literature as a seed sequence in high performing metaheuristics. We demonstrate that using some of our proposed heuristics as seeds yields better final results in comparison.     

Heuristics for scheduling in a flowshop with setup,processing and removal times separated

The problem of scheduling in a flowshop, where setup, processing and removal times are separable, is considered with the objective of minimizing makespan. Heuristic algorithms are developed by the introduction of simplifying assumptions into the scheduling problem under study. An improvement method is incorporated in the heuristics to enhance the quality of their solutions. The proposed heuristics and an existing heuristic are evaluated by a large number of randomly generated problems. The results of an extensive computational investigation for various values of parameters are presented.     

Some heuristic algorithms for total tardiness minimization in a flowshop with blocking

The flowshop scheduling problem with blocking in-process is addressed in this paper. In this environment, there are no buffers between successive machines; therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Heuristic approaches are proposed to minimize the total tardiness criterion. A constructive heuristic that explores specific characteristics of the problem is presented. Moreover, a GRASP-based heuristic is proposed and coupled with a path relinking strategy to search for better outcomes. Computational tests are presented and the comparisons made with an adaptation of the NEH algorithm and with a branch-and-bound algorithm indicate that the new approaches are promising.     

Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm

The blocking flowshop scheduling problem has a strong industrial background but is under-represented in the research literature. In this study, a revised artificial immune system (RAIS) algorithm based on the features of artificial immune systems and the annealing process of simulated annealing algorithms was presented to minimize the makespan in a blocking flowshop. To validate the performance of the proposed RAIS algorithm, computational experiments and comparisons were conducted on the well-known benchmark problems of Taillard used in earlier studies. The experimental results show that the proposed RAIS algorithm outperforms the state-of-art algorithms on the same benchmark problem data set.     

An iterated greedy algorithm for the flowshop scheduling problem with blocking

This paper proposes an iterated greedy algorithm for solving the blocking flowshop scheduling problem for makespan minimization. Moreover, it presents an improved NEH-based heuristic, which is used as the initial solution procedure for the iterated greedy algorithm. The effectiveness of both procedures was tested on some of Taillard’s benchmark instances that are considered to be blocking flowshop instances. The experimental evaluation showed the efficiency of the proposed algorithm, in spite of its simple structure, in comparison with a state-of-the-art algorithm. In addition, new best solutions for Taillard’s instances are reported for this problem, which can be used as a basis of comparison in future studies.     

An efficient approach for large scale graph partitioning

In this paper, we consider the problem of partitioning the set of vertices of a graph intok subsets of approximately the same cardinality in such a way that the number of edges whose endpoints are in different subsets is minimized. A greedy heuristic, called Procedure1, based on the independent growth of each subset by fronts is proposed for constructing a good-quality graph partition. In addition, we present a more sophisticated version of the greedy heuristic, called Procedure2, which periodically calls a routine to refine the partition being built. We show that the partitions generated by Procedure1 are competitive with those obtained by several constructive heuristics in the literature, e.g. spectral, geometric, as well as other greedy heuristics. Moreover, the partitions produced by Procedure2 are compared with those produced by a leading graph partitioning method in the literature.     

A heuristic to minimize total flow time in permutation flow shop

In this paper, we address an n-job, m-machine permutation flow shop scheduling problem for the objective of minimizing the total flow time. We propose a modification of the best-known method of Framinan and Leisten [An efficient constructive heuristic for flowtime minimization in permutation flow shops. Omega 2003;31:311–7] for this problem. We show, through computational experimentation, that this modification significantly improves its performance while not affecting its time-complexity.     

Heuristic algorithms for the two-machine flowshop with limited machine availability

The paper studies a flowshop scheduling problem where machines are not available in given time intervals. The objective is to minimize the makespan. The problem is known to be NP-hard for two machines. We analyze constructive and local search based heuristic algorithms for the two-machine case. The algorithms are tested on easy and difficult test problems with up to 100 jobs and 10 intervals of non-availability. Computational results show that the algorithms perform well. For many problems an optimum solution is found.     

等待时间受限的置换流水车间调度启发式算法

针对等待时间受限的置换流水车间调度问题,分析了其可行解与流水车间调度最优解的关系,给出了计算最大完工时间的有向图,证明了等待时间受限的置换流水车间调度问题的可逆性,并以此为基础提出了一种启发式算法.算法首先根据等待时间受限约束与无等待(no-wait)约束的相似特征,生成初始工件序列集;然后利用问题可逆性给出了复杂度为O(n2m)的插入优化机制,进一步优化初始解.数据实验的结果验证了启发式算法的可行性和有效性.     

Scheduling in an assembly-type production chain with batch transfer

This paper addresses a three-machine assembly-type flowshop scheduling problem, which frequently arises from manufacturing process management as well as from supply chain management. Machines one and two are arranged in parallel for producing component parts individually, and machine three is an assembly line arranged as the second stage of a flowshop for processing the component parts in batches. Whenever a batch is formed on the second-stage machine, a constant setup time is required. The objective is to minimize the makespan. In this study we establish the strong NP-hardness of the problem for the case where all the jobs have the same processing time on the second-stage machine. We then explore a useful property, based upon which a special case can be optimally solved in polynomial time. We also study several heuristic algorithms to generate quality approximate solutions for the general problem. Computational experiments are conducted to evaluate the effectiveness of the algorithms.     

A heuristic for scheduling in a flowshop with the bicriteria of makespan and maximum tardiness minimization

This article deals with the development of a heuristic for scheduling in a flowshop with the objective of minimizing the makespan and maximum tardiness of a job. The heuristic makes use of the simulated annealing technique. The proposed heuristic is relatively evaluated against the existing heuristic for scheduling to minimize the weighted sum of the makespan and maximum tardiness of a job. The results of the computational evaluation reveal that the proposed heuristic performs better than the existing one.     

Parallel machine scheduling subject to auxiliary resource constraints

This paper is motivated by scheduling photolithography machines in semiconductor manufacturing wherein reticle requirements are the auxiliary resource constraints. As the problem is NP hard, two different heuristic solution approaches are developed. The performance of our network-based mathematical model and heuristics are evaluated through an extensive set of problem instances. The best performing heuristic method typically produces solutions that are 1.72% above optimal. If this method is used as the seed solution for a Tabu search-based post processing algorithm, schedules that are 0.78% above the optimal solution, on average, are possible.     

Heuristic for scheduling in a two-machine bicriteria dynamic flowshop with setup and processing times separated

This paper addresses the two-machine bicriteria dynamic flowshop problem where setup time of a job is separated from its processing time and is sequenced independently. The performance considered is the simultaneous minimization of total flowtime and makespan, which is more effective in reducing the total scheduling cost compared to the single objective. A frozen-event procedure is first proposed to transform a dynamic scheduling problem into a static one. To solve the transformed static scheduling problem, an integer programming model with N ² + 5N variables and 7N constraints is formulated. Because the problem is known to be NP-complete, a heuristic algorithm with the complexity of O (N ³) is provided. A decision index is developed as the basis for the heuristic. Experimental results show that the proposed heuristic algorithm is effective and efficient. The average solution quality of the heuristic algorithm is above 99%. A 15-job case requires only 0.0235 s, on average, to obtain a near or even optimal solution.     

Assortment optimisation problem: A distribution-free approach

Assortment optimisation is a critical decision that is regularly made by retailers. The decision involves a trade-off between offering a larger assortment of products but smaller inventories of each product and offering a smaller number of varieties with more inventory of each product. We propose a robust, distribution-free formulation of the assortment optimisation problem such that the assortment and inventory levels can be jointly optimised without making specific assumptions on the demand distributions of each product. We take a max-min approach to the problem that provides a guaranteed lower bound to the expected profit when only the mean and variance of the demand distribution are known. We propose and test three heuristic algorithms that provide solutions in O(nlog (n)) time and identify two cases where one of the heuristics is guaranteed to return optimal policies. Through numerical studies, we demonstrate that one of the heuristics performs extremely well, with an average optimality gap of 0.07% when simulated under varying conditions. We perform a sensitivity analysis of product and store demand attributes on the performance of the heuristic. Finally, we extend the problem by including maximum cardinality constraints on the assortment size and perform numerical studies to test the performance of the heuristics.     

A hybrid genetic algorithm/mathematical programming approach to the multi-family flowshop scheduling problem with lot streaming

This paper presents a hybrid genetic algorithm/mathematical programming heuristic for the n-job, m-machine flowshop problems with lot streaming. The number of sublots for each job and the size of sublots are directly addressed by the heuristic and setups may be sequence-dependent. A new aspect of the problem, the interleaving of sublots from different jobs in the processing sequence, is developed and addressed. Computational results from 12 randomly generated test sets of 24 problems each are presented.     

Scheduling and the problem of computational complexity

Why is it that the problem of scheduling is so computationally difficult to solve? At last recent developments in modern mathematical complexity theory are providing some insights. The paper describes in essentially non-mathematical terms the computational technique known as the ‘Branch and Bound Method’. This, the best general optimising technique available for scheduling, is also shown to have its limitations. It now appears that efficient computational and optimising algorithms are unlikely ever to be found for all except special cases of the general industrial scheduling problem. It seems that heuristic (rule-of-thumb) methods leading to approximate solutions are likely to offer the only real promise for the future.     

基于改进遗传算法的置换装配线调度问题研究

企业的置换装配线调度问题（Permutation Assembly-line Scheduling Problem,PASP）是一类典型的NP-hard型生产调度问题,是现代集成制造系统CIMS极为关心的问题。该问题可以具体描述为n个工件要在m台机器上加工,每个工件需要经过m道工序,每道工序要求不同的机器,这n个工件通过m台机器的顺序相同,它们在每台机器上的加工顺序也相同,问题的主要目标是找到n个工件在每台机器上的最优加工顺序,使得最大完工时间最小。由于PASP问题的NP-hard性质,本文使用遗传算法对其进行求解。尽管遗传算法常用以求解调度问题,但其选择与交叉机制易导致局部最优及收敛慢。因此,本文提出基于区块挖掘与重组的改进遗传算法用于求解置换装配线调度问题。首先通过关联规则挖掘出不同的优秀基因,然后将具有较优结果的基因组合为优势区块,产生具优势的人工解,并引入高收敛性的局部搜索方法,提高搜索到最优解的机会与收敛效率。本文以OR-Library中Taillard标准测试例来验证改进遗传算法的求解质量与效率,结果证明：本文所提算法与其它求解调度问题的现有5种知名算法相比,不仅收敛速度较快,同时求解质量优于它们。     

Scheduling two-stage production lines with multiple machines

Most manufacturing process maintain separate fabrication and assembly centres. Based on this observation, the author coincides a manufacturing process that contains two stages of production with multiple machines. The manufacturer produces a variety of products to satisfy customer demands, operates under a 'push' mode and in a ‘ make-to-order’ environment. Each customer order consists of known quantities of different products which must be delivered as a whole shipment. Periodically, the manufacturer schedules all the accumulated unscheduled customer orders. The scheduling objective is to minimize the sum of weighted customer order lead times. Such manufacturing systems are formulated as a mathematical programming problem. It is then shown that this problem is unary NP-hard and remains unary NP-hard even when all the weights are equal. Some insights about the structure of the optimal schedule(s) are provided and some special cases solved in polynomial time. Several polynomial time heuristics are proposed, and worst-case analysis of some of the heuristics are provided. Tight lower bounds are developed in order to measure the performance of the proposed heuristics. Numerical examples are presented and possible extensions are discussed.     

A Comparative Evaluation of Labor Tour Scheduling Methods

This paper presents an initial study of relative performance for a number of the labor tour scheduling heuristic methods proposed in the literature. These heuristic methods were classified as either linear programming (LP) based or construction. Each of the methods was applied to a tour scheduling problem, subject to a variety of labor demand requirements distributions, with the singular objective being the minimization of total labor hours scheduled. Statistical analysis revealed that effective tour schedule solutions were generated by both LP-based and construction methods. Since the performances of the Keith [13], Morris and Showalter [18], and Bechtold and Showalter [5] methods were superior, their solutions were also compared across a number of secondary criteria. An overall analysis of the performances of these three methods resulted in the identification of a number of important managerial and decision-making issues. We conclude that service operations management should consider integrating these heuristic methods into a decision support system. Finally, suggestions for future research are provided.     

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.