The significance of reducing setup times/setup costs

Scheduling with setup times or setup costs plays a crucial role in todays modern manufacturing and service environments where reliable products/services are to be delivered on time. Scheduling activities profoundly depend on the times/costs required to prepare the facility for performing the activities. However, the vast majority of existing scheduling literature ignores this fact. We define and emphasize the importance, applications, and benefits of explicitly considering setup times/costs in scheduling research. Moreover, a review of the latest research on scheduling problems with setup times/costs is provided.     

Single-machine scheduling against due dates with past-sequence-dependent setup times

Recently Koulamas and Kyparisis [Koulamas, C., Kyparisis, G.J., in press. Single-machine scheduling with past-sequence-dependent setup times. European Journal of Operational Research] introduced past-sequence-dependent setup times to scheduling problems. This means that the setup time of a job is proportionate to the sum of processing times of the jobs already scheduled. Koulamas and Kyparisis [Koulamas, C., Kyparisis, G.J., in press. Single-machine scheduling with past-sequence-dependent setup times. European Journal of Operational Research] were able to show for a number of single-machine scheduling problems with completion time goals that they remain polynomially solvable. In this paper we extend the analysis to problems with due dates. We demonstrated that some problems remain polynomially solvable. However, for some other problems well-known polynomially solution approaches do not guarantee optimality any longer. Consequently we concentrated on finding polynomially solvable special cases.     

An Enhanced TSP-Based Heuristic for Makespan Minimization in a Flow Shop with Setup Times

This paper presents an enhanced heuristic for minimizing the makespan of the flow shop scheduling problem with sequence-dependent setup times. The procedure transforms an instance of the problem into an instance of the traveling salesman problem by introducing a cost function that penalizes for both large setup times and bad fitness of schedule. This hybrid cost function is an improvement over earlier approaches that penalized for setup times only, ignoring the flow shop aspect of the problem. To establish good parameter values, each component of the heuristic was evaluated computationally over a wide range of problem instances. In the testing stage, an experimental comparison with a greedy randomized adaptive search procedure revealed the conditions and data attributes where the proposed procedure works best.     

A new neighborhood and tabu search for the Blocking Job Shop

The Blocking Job Shop is a version of the job shop scheduling problem with no intermediate buffers, where a job has to wait on a machine until being processed on the next machine. We study a generalization of this problem which takes into account transfer operations between machines and sequence-dependent setup times. After formulating the problem in a generalized disjunctive graph, we develop a neighborhood for local search. In contrast to the classical job shop, there is no easy mechanism for generating feasible neighbor solutions. We establish two structural properties of the underlying disjunctive graph, the concept of closures and a key result on short cycles, which enable us to construct feasible neighbors by exchanging critical arcs together with some other arcs. Based on this neighborhood, we devise a tabu search algorithm and report on extensive computational experience, showing that our solutions improve most of the benchmark results found in the literature.     

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

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

重入排序问题综述

重入排序问题打破传统假设：工件在加工过程中不止一次地访问某台机器,是一种新型的排序问题. 重入的特点源于半导体生产, 并广泛存在于其他领域. 对重入排序问题已有文献中的成果进行梳理和分析,按问题所处机器环境的不同, 对内容和方法进行分类介绍和总结：包括单机问题、流水作业问题、混合流水作业问题及其他机器环境下的重入排序问题. 最后展望未来的趋势和研究方向.     

Survey on fuzzy shop scheduling

The real life scheduling problems often have several uncertainties. The solutions of these problems can provide deeper insights to the decision maker than those of deterministic problems. Fuzzy set theory as most important tool to model uncertainty represents an attractive tool to aid research in the production management. Since to the best of our knowledge, there is not a comprehensive review on the fuzzy scheduling literature, the goal of this paper is to provide an extensive review for the fuzzy machine scheduling which it covers more than 140 papers. For this purpose, first, this paper classifies and reviews the literature according to shop environments, including single machine, parallel machines, flowshop, job shop and open shop. Then the reviewed literature is quantified and measured. At the end the paper concludes by presenting some problems receiving less attention than the others and proposing some research opportunities in the field.     

An optimization-based heuristic for the robotic cell problem

This study investigates an optimization-based heuristic for the robotic cell problem. This problem arises in automated cells and is a complex flow shop problem with a single transportation robot and a blocking constraint. We propose an approximate decomposition algorithm. The proposed approach breaks the problem into two scheduling problems that are solved sequentially: a flow shop problem with additional constraints (blocking and transportation times) and a single machine problem with precedence constraints, time lags, and setup times. For each of these problems, we propose an exact branch-and-bound algorithm. Also, we describe a genetic algorithm that includes, as a mutation operator, a local search procedure. We report the results of a computational study that provides evidence that the proposed optimization-based approach delivers high-quality solutions and consistently outperforms the genetic algorithm. However, the genetic algorithm delivers reasonably good solutions while requiring significantly shorter CPU times.     

A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations

A hybrid flow shop scheduling problem (HFSP) with assembly operations is studied in this paper. In the considered problem, a number of products of the same kind are produced. Each product is assembled using a set of several parts. At first, the parts are produced in a hybrid flow shop and then they are assembled in an assembly stage to produce products. The considered objective is to minimize the completion time of all products (makespan). This problem has been proved strongly NP-hard, so in order to solve it, a hierarchical branch and bound algorithm is presented. Also, some lower and upper bounds are developed to increase the efficiency of the proposed algorithm. The numerical experiments are used to evaluate the performance of the proposed algorithm.     

Routing open shop and flow shop scheduling problems

We consider a generalization of the classical open shop and flow shop scheduling problems where the jobs are located at the vertices of an undirected graph and the machines, initially located at the same vertex, have to travel along the graph to process the jobs. The objective is to minimize the makespan. In the tour-version the makespan means the time by which each machine has processed all jobs and returned to the initial location. While in the path-version the makespan represents the maximum completion time of the jobs. We present improved approximation algorithms for various cases of the open shop problem on a general graph, and the tour-version of the two-machine flow shop problem on a tree. Also, we prove that both versions of the latter problem are NP-hard, which answers an open question posed in the literature.     

On non-permutation solutions to some two machine flow shop scheduling problems

In this paper, we study two versions of the two machine flow shop scheduling problem, where schedule length is to be minimized. First, we consider the two machine flow shop with setup, processing, and removal times separated. It is shown that an optimal solution need not be a permutation schedule, and that the problem isNP-hard in the strong sense, which contradicts some known results. The tight worst-case bound for an optimal permutation solution in proportion to a global optimal solution is shown to be 3/2. An O(n) approximation algorithm with this bound is presented. Secondly, we consider the two machine flow shop with finite storage capacity. Again, it is shown that there may not exist an optimal solution that is a permutation schedule, and that the problem isNP-hard in the strong sense.     

Optimal policies in stochastic shop scheduling

In this paper a survey is presented of some of the recent results in stochastic open shop, flow shop and job shop scheduling. The distributions of the processing times of the jobs are known in advance, but the actual processing times are not known in advance. The jobs may have due dates. Optimal preemptive and nonpreemptive policies are determined for the minimization of various objective functions, such as the expected makespan, the expected flow time and the expected number of late jobs. The effect of various degrees of dependence between the processing times of any given job on the various machines is investigated. Under given conditions bounds are obtained for the expected makespan in the different models.Partially supported by the National Science Foundation (NSF), under grant ECS-8115344 with the Georgia Institute of Technology.     

Approximation algorithms for UET scheduling problems with exact delays

In this paper we consider coupled-task single-machine and two-machine flow shop scheduling problems with exact delays, unit processing times, and the makespan as an objective function. The main results of the paper are fast 7/4- and 3/2-approximation algorithms for solving the single- and two-machine problems, respectively.     

Mixed integer goal programming models for the flexible job-shop scheduling problems with separable and non-separable sequence dependent setup times

The optimization problem addressed in this paper is an advanced form of the flexible job shop scheduling problem (FJSP) which also covers process plan flexibility and separable/non-separable sequence dependent setup times in addition to routing flexibility. Upon transforming the problem into an equivalent network problem, two mixed integer goal programming models are formulated. In the first model (Model A) the sequence dependent setup times are non-separable. In the second one (Model B) they are separable. Model B is obtained from Model A with a minor modification. The formulation of the models is described on a small sized numerical example and the solutions are interpreted. Finally, computational results are obtained on test problems.     

Scheduling open shops with parallel machines

The parallel shop and the open shop are two machine environments that have received much attention in the literature of scheduling theory. A common generalization—the open shop with parallel machines—is considered in this paper. Polynomial-time algorithms are presented for obtaining minimum-length preemptive schedules for three cases. Open shops with single-operation machines of equal speed are scheduled with essentially no more difficulty than an ordinary open shop. Open shops with multiple-operation machines of equal speed are scheduled with the aid of a sequence of network flow computations. The general open shop problem with parallel machines of arbitrary speeds can be solved by linear programming, in much the same way as an optimal preemptive schedule can be found for unrelated parallel machines.     

Modeling job shop scheduling with batches and setup times by timed Petri nets

Batch and setup times are two important factors in practical job shop scheduling. This paper proposes a method to model job shop scheduling problems including batches and anticipatory sequence-dependent setup times by timed Petri nets. The general modeling method is formally presented. The free choice property of the model is proved. A case study extracted from practical scheduling is given to show the feasibility of the modeling method. Comparison with some previous work shows that our model is more compact and effective in finding the best solution.     

Scheduling jobs with a general learning effect model

The paper deals with machine scheduling problems with a general learning effect. By the general learning effect, we mean that the actual processing time of a job is not only a non-increasing function of the total weighted normal processing times of the jobs already processed, but also a non-increasing function of the job’s position in the sequence, where the weight is a position-dependent weight. We show that even with the introduction of a general learning effect to job processing times, some single machine scheduling problems are still polynomially solvable under the proposed model. We also show that some special cases of the flow shop scheduling problems can be solved in polynomial time.     

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.     

Online scheduling of ordered flow shops

We consider online as well as offline scheduling of ordered flow shops with the makespan as objective. In an online flow shop scheduling problem, jobs are revealed to a decisionmaker one by one going down a list. When a job is revealed to the decision maker, its operations have to be scheduled irrevocably without having any information regarding jobs that will be revealed afterwards. We consider for the online setting the so-called Greedy Algorithm which generates permutation schedules in which the jobs on the machines are at all times processed without any unnecessary delays. We focus on ordered flow shops, in particular proportionate flow shops with different speeds and proportionate flow shops with different setup times. We analyze the competitive ratio of the Greedy Algorithm for such flow shops in the online setting. For several cases, we derive lower bounds on the competitive ratios.     

Hybrid flow shop scheduling with sequence dependent family setup time and uncertain due dates

This paper studies the scheduling problem in hybrid flow shop (HFS) environment. The sequence dependent family setup time (SDFST) is concerned with minimization of makespan and total tardiness. Production environments in real world include innumerable cases of uncertainty and stochasticity of events and a suitable scheduling model should consider them. Hence, in this paper, due date is assumed to be uncertain and its data follow a normal distribution. Since the proposed problem is NP-hard, two metaheuristic algorithms are presented based on genetic algorithm, namely: Non-dominated Sorting Genetic Algorithm (NSGAII) and Multi Objective Genetic Algorithm (MOGA). The quantitative and qualitative results of these two algorithms have been compared in different dimensions with multi phase genetic algorithm (MPGA) used in literature review. Experimental results indicate that the NSGAII performs very well when compared against MOGA and MPGA in a considerably shorter time.