A Rollout Metaheuristic for Job Shop Scheduling Problems

In this paper we deal with solution algorithms for a general formulation of the job shop problem, called alternative graph. We study in particular the job shop scheduling problem with blocking and/or no-wait constraints. Most of the key properties developed for solving the job shop problem with infinite capacity buffer do not hold in the more general alternative graph model. In this paper we report on an extensive study on the applicability of a metaheuristic approach, called rollout or pilot method. Its basic idea is a look-ahead strategy, guided by one or more subheuristics, called pilot heuristics. Our results indicate that this method is competitive and very promising for solving complex scheduling problems.     

Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops

In this paper, we consider 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 (Wafer Fabs) are typical examples for manufacturing systems with these characteristics. Our primary performance measure is total weighted tardiness (TWT). The shifting bottleneck heuristic uses a disjunctive graph to decompose the overall scheduling into scheduling problems for single tool groups. The scheduling algorithms for these scheduling problems are called subproblem solution procedures (SSPs). In previous research, only subproblem solution procedures based on dispatching rules have been considered. In this paper, we are interested in how much we can gain in terms of TWT if we apply more sophisticated subproblem solution procedures like genetic algorithms for parallel machine scheduling. We conduct simulation experiments in a dynamic job shop environment in order to assess the performance of the suggested subproblem solution procedures. It turns out that using near to optimal subproblem solution procedures leads in many situations to improved results compared to dispatching-based subproblem solution procedures.     

An Ant Colony Optimization Algorithm for Shop Scheduling Problems

We deal with the application of ant colony optimization to group shop scheduling, which is a general shop scheduling problem that includes, among others, the open shop scheduling problem and the job shop scheduling problem as special cases. The contributions of this paper are twofold. First, we propose a neighborhood structure for this problem by extending the well-known neighborhood structure derived by Nowicki and Smutnicki for the job shop scheduling problem. Then, we develop an ant colony optimization approach, which uses a strong non-delay guidance for constructing solutions and which employs black-box local search procedures to improve the constructed solutions. We compare this algorithm to an adaptation of the tabu search by Nowicki and Smutnicki to group shop scheduling. Despite its general nature, our algorithm works particularly well when applied to open shop scheduling instances, where it improves the best known solutions for 15 of the 28 tested instances. Moreover, our algorithm is the first competitive ant colony optimization approach for job shop scheduling instances.     

排序在车间生产管理中的应用

本文结合上海第一机床厂的实际，论述建立车间生产调度决策支持系统的必要性，详细阐明这个决策支持系统的设计原理与系统结构，并介绍开发的相应软件系统的特点和功能及排序论的研究成果在其中的应用．     

Trapezoidal type inequalities for n-time differentiable functions

In this paper we consider the flow shop scheduling problems with the effects of learning and deterioration. In this model the processing times of a job is defined as a function of its starting time and position in a sequence. The scheduling objective functions are makespan and total completion time. We prove that even with the introduction of learning effect and deteriorating jobs to job processing times, some special flow shop scheduling problems remain polynomially solvable.     

An iterated greedy metaheuristic for the blocking job shop scheduling problem

In this paper we consider a job shop scheduling problem with blocking (BJSS) constraints. Blocking constraints model the absence of buffers (zero buffer), whereas in the traditional job shop scheduling model buffers have infinite capacity. There are two known variants of this problem, namely the blocking job shop scheduling with swap allowed (BWS) and the one with no swap allowed (BNS). This scheduling problem is receiving an increasing interest in the recent literature, and we propose an Iterated Greedy (IG) algorithm to solve both variants of the problem. IG is a metaheuristic based on the repetition of a destruction phase, which removes part of the solution, and a construction phase, in which a new solution is obtained by applying an underlying greedy algorithm starting from the partial solution. A comparison with recent published results shows that the iterated greedy algorithm outperforms other state-of-the-art algorithms on benchmark instances. Moreover it is conceptually easy to implement and has a broad applicability to other constrained scheduling problems.     

Decomposition approaches in permutation scheduling problems with application to the M-machine flow shop scheduling problems

In this article, we consider three decomposition techniques for permutation scheduling problems. We introduce a general iterative decomposition algorithm for permutation scheduling problems and apply it to the permutation flow shop scheduling problem. We also develop bounds needed for this iterative decomposition approach and compare its computational requirements to that of the traditional branch and bound algorithms. Two heuristic algorithms based on the iterative decomposition approach are also developed. extensive numerical study indicates that the heuristic algorithms are practical alternatives to very costly exact algorithms for large flow shop scheduling problems.     

Local search algorithms for the multiprocessor flow shop scheduling problem

The multiprocessor flow shop scheduling problem is a generalization of the ordinary flow shop scheduling problem. The problem consists of both assigning operations to machines and scheduling the operations assigned to the same machine. We review the literature on local search methods for flow shop and job shop scheduling and adapt them to the multiprocessor flow shop scheduling problem. Other local search approaches we consider are variable-depth search and simulated annealing. We show that tabu search and variable-depth search with a neighborhood originated by Nowicki and Smutnicki outperform the other 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.     

Constraint-Based Job Shop Scheduling with IILOG SCHEDULER

We introduce constraint-based scheduling and discuss its main principles. An approximation algorithm based on tree search is developed for the job shop scheduling problem using ILOG SCHEDULER. A new way of calculating lower bounds on the makespan of the job shop scheduling problem is presented and we show how such results can be used within a constraint-based approach. An empirical performance analysis shows that the algorithm we developed performs well. Finally, taking the job shop scheduling problem as a start point, we discuss how constraint-based scheduling can be used to solve more general scheduling problems.     

Properties of optimal schedules in preemptive shop scheduling

In this work we show that certain classical preemptive shop scheduling problems with integral data satisfy the following integer preemption property: there exists an optimal preemptive schedule where all interruptions and all starting and completion times occur at integral dates. We also give new upper bounds on the minimal number of interruptions for various shop scheduling problems.     

Games,Critical Paths and Assignment Problems in Permutation Flow Shops and Cyclic Scheduling Flow Line Environments

In this paper we address the non-pre-emptive flow shop scheduling problem for makespan minimization in a new modelling framework. A lower bound generation scheme is developed by using appropriately defined linear assignment problems and, based on this new approach, a special class of permutation flow shop problems is identified. We present a game theoretic interpretation of our modelling approach which leads to an integer programming formulation of the scheduling problem. A new branch and bound scheme is developed based on these results. The major advantage of our modelling framework and branch-and- bound approach is that it can be easily extended to address a general class of cyclic scheduling problems for production flow lines with blocking. After a discussion of this extension, we report on computational experience that indicates the very satisfactory performance of the new optimal solution procedure for cyclic scheduling problems with finite capacity buffers.     

A computational study of constraint satisfaction for multiple capacitated job shop scheduling

We introduce the multiple capacitated job shop scheduling problem as a generalization of the job shop scheduling problem. In this problem machines may process several operations simultaneously. We present an algorithm based on constraint satisfaction techniques to handle the problem effectively. The most important novel feature of our algorithm is the consistency checking. An empirical performance analysis is performed using a well-known set of instances of the job shop scheduling problem and a newly constructed set of instances of the multiple capacitated job shop scheduling problem. We show that our algorithm performs well for both sets of instances.     

安装、加工和拆卸时间分离的两台机器混合作业问题

混合作业是经典的自由作业和异序作业的一种综合,其中一些工件可以按任意的机器顺序进行处理,而另一些工件必须遵守预先指定的机器顺序.本文研究安装、加工和拆卸时间分离的两台机器混合作业排序问题,该问题已经被知道是强NP困难的,本文把流水作业中的同顺序作业概念推广到混合作业,并得到这个混合作业问题在同顺序意义下的最优解,这个解对于一般情形是3/2近似解,但对于一些有意义的特殊情形是整体最优的.     

A survey of scheduling problems with setup times or costs

The first comprehensive survey paper on scheduling problems with separate setup times or costs was conducted by [Allahverdi, A., Gupta, J.N.D., Aldowaisan, T., 1999. A review of scheduling research involving setup considerations. OMEGA The International Journal of Management Sciences 27, 219–239], who reviewed the literature since the mid-1960s. Since the appearance of that survey paper, there has been an increasing interest in scheduling problems with setup times (costs) with an average of more than 40 papers per year being added to the literature. The objective of this paper is to provide an extensive review of the scheduling literature on models with setup times (costs) from then to date covering more than 300 papers. Given that so many papers have appeared in a short time, there are cases where different researchers addressed the same problem independently, and sometimes by using even the same technique, e.g., genetic algorithm. Throughout the paper we identify such areas where independently developed techniques need to be compared. The paper classifies scheduling problems into those with batching and non-batching considerations, and with sequence-independent and sequence-dependent setup times. It further categorizes the literature according to shop environments, including single-machine, parallel machines, flow shop, no-wait flow shop, flexible flow shop, job shop, open shop, and others.     

NP-hard cases in scheduling deteriorating jobs on dedicated machines

In this paper problems of time-dependent scheduling on dedicated machines are considered. The processing time of each job is described by a function which is dependent on the starting time of the job. The objective is to minimise the maximum completion time (makespan). We prove that under linear deterioration the two-machine flow shop problem is strongly NP-hard and the two-machine open shop problem is ordinarily NP-hard. We show that for the three-machine flow shop and simple linear deterioration there does not exist a polynomial-time approximation algorithm with the worst case ratio bounded by a constant, unless P=NP. We also prove that the three-machine open shop problem with simple linear deterioration is ordinarily NP-hard, even if the jobs have got equal deterioration rates on the third machine.     

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.     

Bilevel programming approach applied to the flow shop scheduling problem under fuzziness

This paper presents a fuzzy bilevel programming approach to solve the flow shop scheduling problem. The problem considered here differs from the standard form in that operators are assigned to the machines and imposing a hierarchy of two decision makers with fuzzy processing times. The shop owner considered higher level and assigns the jobs to the machines in order to minimize the flow time while the customer is the lower level and decides on a job schedule in order to minimize the makespan. In this paper, we use the concepts of tolerance membership function at each level to define a fuzzy decision model for generating optimal (satisfactory) solution for bilevel flow shop scheduling problem. A solution algorithm for solving this problem is given. Mathematics Subject Classification: 90C70, 90B36, 90C99     

A genetic algorithm for flow shop scheduling problems

Many scheduling problems are NP-hard problems. For such NP-hard combinatorial optimization problems, heuristics play a major role in searching for near-optimal solutions. In this paper we develop a genetic algorithm-based heuristic for the flow shop scheduling problem with makespan as the criterion. The performance of the algorithm is compared with the established NEH algorithm. Computational experience indicates that genetic algorithms can be good techniques for flowshop scheduling problems.