A Computational Study of Shifting Bottleneck Procedures for Shop Scheduling Problems

We examine the performance of Shifting Bottleneck (SB) heuristics for shop scheduling problems where the performance measure to be minimized is makespan (C _max) or maximum lateness (L _max). Extensive computational experiments are conducted on benchmark problems from the literature as well as several thousand randomly generated test problems with three different routing structures and up to 1000 operations. Several different versions of SB are examined to determine the effect on solution quality and time of different subproblem solution procedures, reoptimization procedures and bottleneck selection criteria. Results show that the performance of SB is significantly affected by job routings, and that SB with optimal subproblem solutions and full reoptimization at each iteration consistently outperforms dispatching rules, but requires high computation times for large problems. High quality subproblem solutions and reoptimization procedures are essential to obtaining good solutions. We also show that schedules developed by SB to minimize L _max perform well with respect to several other performance measures, rendering them more attractive for practical use.     

Heuristic and stochastic methods in optimization

The shifting bottleneck (SB) heuristic is among the most successful approximation methods for solving the job shop problem. It is essentially a machine based decomposition procedure where a series of one machine sequencing problems (OMSPs) are solved. However, such a procedure has been reported to be highly ineffective for the flow shop problems. In particular, we show that for the 2-machine flow shop problem, the SB heuristic will deliver the optimal solution in only a small number of instances. We examine the reason behind the failure of the machine based decomposition method for the flow shop. An optimal machine based decomposition procedure is formulated for the 2-machine flow shop, the time complexity of which is worse than that of the celebrated Johnson’s rule. The contribution of the present study lies in showing that the same machine based decomposition procedures which are so successful in solving complex job shops can also be suitably modified to optimally solve the simpler flow shops.     

Hybrid Rollout Approaches for the Job Shop Scheduling Problem

In this paper, we focus on heuristic approaches for solving the deterministic job shop scheduling problem. More specifically, a new priority dispatch rule and hybrid rollout algorithms are developed for approaching the problem under consideration. The proposed solution algorithms are tested on a set of instances taken from the literature and compared with other methods. The computational results validate the effectiveness of the developed solution approaches and show that the proposed rollout algorithms are competitive with respect to several state-of-art heuristics for solving the job shop scheduling problem. The author thanks Dr. Marco Mancini and Dr. Alessandro Tarasio for valuable suggestions about computational issues.     

Tabu search for graph partitioning

In this paper, we develop a tabu search procedure for solving the uniform graph partitioning problem. Tabu search, an abstract heuristic search method, has been shown to have promise in solving several NP-hard problems, such as job shop and flow shop scheduling, vehicle routing, quadratic assignment, and maximum satisfiability. We compare tabu search to other heuristic procedures for graph partitioning, and demonstrate that tabu search is superior to other solution approaches for the uniform graph partitioning problem both with respect to solution quality and computational requirements.     

A filter-and-fan approach to the job shop scheduling problem

The job shop scheduling problem (JSSP) is a notoriously difficult problem in combinatorial optimization. Extensive investigation has been devoted to developing efficient algorithms to find optimal or near-optimal solutions. This paper proposes a new heuristic algorithm for the JSSP that effectively combines the classical shifting bottleneck procedure (SBP) with a dynamic and adaptive neighborhood search procedure. Our new search method, based on a filter-and-fan (F&F) procedure, uses the SBP as a subroutine to generate a starting solution and to enhance the best schedules produced. The F&F approach is a local search procedure that generates compound moves by a strategically abbreviated form of tree search. Computational results carried out on a standard set of 43 benchmark problems show that our F&F algorithm performs more robustly and effectively than a number of leading metaheuristic algorithms and rivals the best of these algorithms.     

Two-stage open shop scheduling with a bottleneck machine

It is known that for the open shop scheduling problem to minimize the makespan there exists no polynomial-time heuristic algorithm that guarantees a worst-case performance ratio better than 5/4, unless P≠NP. However, this result holds only if the instance of the problem contains jobs consisting of at least three operations. This paper considers the open shop scheduling problem, provided that each job consists of at most two operations, one of which is to be processed on one of the m⩾2 machines, while the other operation must be performed on the bottleneck machine, the same for all jobs. For this NP-hard problem we present a heuristic algorithm and show that its worst-case performance ratio is 5/4.     

Minimizing maximum completion time in a proportionate flow shop with one machine of different speed

A flow shop with identical machines is called a proportionate flow shop. In this paper, we consider the variant of the n-job, m-machine proportionate flow shop scheduling problem in which only one machine is different and job processing times are inversely proportional to machine speeds. The objective is to minimize maximum completion time. We describe some optimality conditions and show that the problem is NP-complete. We provide two heuristic procedures whose worst-case performance ratio is less than two. Extensive experiments with various sizes are conducted to show the performance of the proposed heuristics.     

Scheduling open shops with parallel machines to minimize total completion time

This paper explores scheduling a realistic variant of open shops with parallel machines per working stage. Since real production floors seldom employ a single machine for each operation, the regular open shop problem is very often in practice extended with a set of parallel machines at each stage. The purpose of duplicating machines in parallel is to either eliminate or to reduce the impact of bottleneck stages on the overall shop efficiency. The objective is to find the sequence which minimizes total completion times of jobs. We first formulate the problem as an effective mixed integer linear programming model, and then we employ memetic algorithms to solve the problem. We employ Taguchi method to evaluate the effects of different operators and parameters on the performance of memetic algorithm. To further enhance the memetic algorithm, we hybridize it with a simple form of simulated annealing as its local search engine. To assess the performance of the model and algorithms, we establish two computational experiments. The first one is small-sized instances by which the model and general performance of the algorithms are evaluated. The second one consists of large-sized instances by which we further evaluate the algorithms.     

Two-machine shop scheduling: Compromise between flexibility and makespan value

In this paper, we consider the problem of providing flexibility to solutions of two-machine shop scheduling problems. We use the concept of group-scheduling to characterize a whole set of schedules so as to provide more choice to the decision-maker at any decision point. A group-schedule is a sequence of groups of permutable operations defined on each machine where each group is such that any permutation of the operations inside the group leads to a feasible schedule. Flexibility of a solution and its makespan are often conflicting, thus we search for a compromise between a low number of groups and a small value of makespan. We resolve the complexity status of the relevant problems for the two-machine flow shop, job shop and open shop. A number of approximation algorithms are developed and their worst-case performance is analyzed. For the flow shop, an effective heuristic algorithm is proposed and the results of computational experiments are reported.     

DBR理论求解柔性作业车间调度问题

针对柔性作业车间调度完工时间最小问题,提出一种结合DBR(鼓-缓冲器-绳子)理论和改进遗传算法的方法。在问题初始化时,建立瓶颈机器识别机制改善初始化方法,提高初始解的质量;在运算过程中依据关键路径建立瓶颈机器的识别机制和调度策略。为了更好保留每代中的优良解,采用外部精英库对优良解进行解保留。运用提出的算法求解基准测试问题,实验结果验证了算法的可行性和有效性。     

Heuristics for a two-stage hybrid flowshop scheduling problem with ready times and a product-mix ratio constraint

This paper focuses on the scheduling problem of minimizing makespan for a given set of jobs in a two-stage hybrid flowshop subject to a product-mix ratio constraint. There are identical parallel machines at the first stage of the hybrid flowshop, while there is a single batch-processing machine at the second stage. Ready times of the jobs (at the first stage) may be different, and a given product-mix ratio of job types should be kept in each batch at the second stage. We present three types of heuristic algorithms: forward scheduling algorithms, backward scheduling algorithms, and iterative algorithms. To evaluate performance of the suggested algorithms, a series of computational experiments are performed on randomly generated test problems and results are reported.     

Flow shop scheduling jobs with position-dependent processing times

The paper is devoted to some flow shop scheduling problems, where job processing times are defined by functions dependent on their positions in the schedule. An example is constructed to show that the classical Johnson's rule is not the optimal solution for two different models of the two-machine flow shop scheduling to minimize makespan. In order to solve the makespan minimization problem in the two-machine flow shop scheduling, we suggest Johnson's rule as a heuristic algorithm, for which the worst-case bound is calculated. We find polynomial time solutions to some special cases of the considered problems for the following optimization criteria: the weighted sum of completion times and maximum lateness. Some furthermore extensions of the problems are also shown.     

Heuristic constructive algorithms for open shop scheduling to minimize mean flow time

In this paper, we consider the problem of scheduling n jobs on m machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. For this strongly NP-hard problem, we develop and discuss different constructive heuristic algorithms. Extensive computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The quality of the solutions is evaluated by a lower bound for the corresponding preemptive open shop problem and by an alternative estimate of mean flow time. We observe that the recommendation of an appropriate constructive algorithm strongly depends on the ratio n/m.     

Worst-case analysis for flow shop scheduling problems with an exponential learning effect

A real industrial production phenomenon, referred to as learning effects, has drawn increasing attention. However, most research on this issue considers only single machine problems. Motivated by this limitation, this paper considers flow shop scheduling problems with an exponential learning effect. By the exponential learning effect, we mean that the processing time of a job is defined by an exponent function of its position in a processing permutation. The objective is to minimize one of the four regular performance criteria, namely, the total completion time, the total weighted completion time, the discounted total weighted completion time, and the sum of the quadratic job completion times. We present heuristic algorithms by using the optimal permutations for the corresponding single-machine scheduling problems. We also analyse the worst-case bound of our heuristic algorithms.     

Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop

This paper considers the problem of scheduling n jobs on m machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. It continues recent work by Bräsel et al. [H. Bräsel, A. Herms, M. Mörig, T. Tautenhahn, T. Tusch, F. Werner, Heuristic constructive algorithms for open shop scheduling to minmize mean flow time, European J. Oper. Res., in press (doi.10.1016/j.ejor.2007.02.057)] on constructive algorithms. For this strongly NP-hard problem, we present two iterative algorithms, namely a simulated annealing and a genetic algorithm. For the simulated annealing algorithm, several neighborhoods are suggested and tested together with the control parameters of the algorithm. For the genetic algorithm, new genetic operators are suggested based on the representation of a solution by the rank matrix describing the job and machine orders. Extensive computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The algorithms are compared relative to each other, and the quality of the results is also estimated partially by a lower bound for the corresponding preemptive open shop problem. For most of the problems, the genetic algorithm is superior when fixing the same number of 30 000 generated solutions for each algorithm. However, in contrast to makespan minimization problems, where the focus is on problems with an equal number of jobs and machines, it turns out that problems with a larger number of jobs than machines are the hardest problems.     

Minimizing makespan in parallel flowshops

In this study, a new class of proportional parallel flow shop problems with the objective of minimizing the makespan has been addressed. A special case for this problem in which jobs are processed on only one machine as opposed to two or more machines in a flow shop, is the well-known multiple processor problem which is NP-complete. The parallel processor problem is a restricted version of the problems addressed in this paper and hence are NP-complete. We develop and test heuristic and simulation approaches to solve large scale problems, while using exact procedures for smaller problems. The performance of the heuristics relative to the LP lower bound as well as a comparison with the truncated integer programming solution are reported. The performance of the heuristics and the simulation results were encouraging.     

A variable neighbourhood search for hybrid flow-shop scheduling problem with rework and set-up times

This paper deals with hybrid flow-shop scheduling problem with rework. In this problem, jobs are inspected at the last stage, and poorly processed jobs were returned and processed again. Thus, a job may visit a stage more than once, and we have a hybrid flow-shop with re-entrant flow. This kind of a shop may occur in many industries, such as final inspection system in automotive manufacturing. The criterion is to minimize the makespan of the system. We developed a 0–1 mixed-integer program of the problem. Since the hybrid flow-shop scheduling problem is NP-hard, an algorithm for finding an optimal solution in polynomial time does not exist. So we generalized some heuristic methods based on several basic dispatching rules and proposed a variable neighbourhood search (VNS) for the problem with sequence-dependent set-up times and unrelated parallel machines. The computational experiments show that VNS provides better solutions than heuristic methods.     

Minimizing the number of machines with limited workload capacity for scheduling jobs with interval constraints

In this paper, we consider a parallel machine scheduling problem in which machines have a limited workload capacity and jobs have deadlines and release dates. The problem is motivated by the operation of energy storage management systems for microgrids under emergency conditions and generalizes some problems that have already been studied in the literature for their theoretical value. In this work, we propose heuristic and exact algorithms to solve the problem. The heuristics are adaptations of classical bin packing heuristics in which additional conditions on the feasibility of a solution are imposed, whereas the exact method is a branch-and-price approach. The results show that the branch-and-price approach is able to optimally solve random instances with up to 250 jobs within a time limit of one hour, while the heuristic procedures provide near optimal solution within reduced running times. Finally, we also provide additional complexity results for a special case of the problem.     

An alternative framework to Lagrangian relaxation approach for job shop scheduling

A new Lagrangian relaxation (LR) approach is developed for job shop scheduling problems. In the approach, operation precedence constraints rather than machine capacity constraints are relaxed. The relaxed problem is decomposed into single or parallel machine scheduling subproblems. These subproblems, which are NP-complete in general, are approximately solved by using fast heuristic algorithms. The dual problem is solved by using a recently developed “surrogate subgradient method” that allows approximate optimization of the subproblems. Since the algorithms for subproblems do not depend on the time horizon of the scheduling problems and are very fast, our new LR approach is efficient, particularly for large problems with long time horizons. For these problems, the machine decomposition-based LR approach requires much less memory and computation time as compared to a part decomposition-based approach as demonstrated by numerical testing.     

Some results of the worst-case analysis for flow shop scheduling with a learning effect

This article considers flow shop scheduling problems with a learning effect. By the learning effect, we mean that the processing time of a job is defined by a function of its position in a processing permutation. The objective is to minimize the total weighted completion time. Some heuristic algorithms by using the optimal permutations for the corresponding single machine scheduling problems are presented, and the worst-case bound of these heuristics are also analyzed.