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.     

A note on flow shop scheduling problems with deteriorating jobs on no-idle dominant machines

The main results in a recent paper [M. Cheng, S. Sun, L. He, Flow shop scheduling problems with deteriorating jobs on no-idle dominant machines, European Journal of Operational Research 183 (2007) 115–124] are incorrect because job processing times are variable due to deteriorating effect, which is not taken into account by the authors. In this note, we show first by counter-examples that the published results are incorrect, and then we provide corrected results.     

A note on the two-stage assembly flow shop scheduling problem with uniform parallel machines

We study the problem of minimizing the makespan in a two-stage assembly flow shop scheduling problem with uniform parallel machines. This problem is a generalization of the assembly flow shop problem with concurrent operations in the first stage and a single assembly operation in the second stage. We propose a heuristic with an absolute performance bound which becomes asymptotically optimal as the number of jobs becomes very large. We show that our results slightly improve earlier results for the simpler assembly flow shop problem (without uniform machines) and for the two-stage hybrid flow shop problem with uniform machines.     

Two-machine flow shop scheduling problems with no-wait jobs

In this paper we provide a fairly complete complexity classification of various versions of the two-machine permutation flow shop scheduling problem to minimize the makespan in which some of the jobs have to be processed with no-wait in process. For some version, we offer a fully polynomial-time approximation scheme and a -approximation algorithm.     

The flow shop problem with no-idle constraints: A review and approximation

The makespan minimization problem in flow shops with no-idle constraints on machines is considered. The latter means that each machine, once started, must process all its operations without intermediate idle time until all those operations are completed. The problem is known to be strongly NP-hard already for three machines. While being based on a geometrical approach, we propose several polynomial time heuristics (for the general case and for special cases of 3 and 4 machines) which provide asymptotically optimal solutions for the increasing number of jobs. A comprehensive review of relevant results is also presented.     

A note of using effective immune based approach for the flow shop scheduling with buffers

This note considers flow shop scheduling with buffers. The objective is to minimize the makespan. As we know, such a problem has several applications in manufacturing and has gained wide attention both in academic and engineering fields. In this note, we propose an immune based approach (IA) to solve this NP-hard problem. Numerical results of 29 benchmark problems from the OR-Library are reported and compared with those of a hybrid genetic algorithm (HGA). As shown, the proposed IA is effective and robust. The solutions by proposed IA are superior to those of HGA reported in the literature. In addition, the average of the relative errors of the proposed IA is only 0.85% for 29 instances with infinite buffers. Limited numerical results show that, as expected, buffer size has a great impact on the scheduling objective especially for larger-scale instances, and there are also significant differences with or without buffers for all instances. But the effect of increasing buffer size from 1 up to 2, 4 or ∞ decreases drastically for all instances.     

A note on the proportionate flow shop with a bottleneck machine

Choi, B.-C., Yoon, S.-H., Chung, S.-J., 2007. Minimizing maximum completion time in a proportionate flow shop with one machine of different speed. European Journal of Operational Research 176, 964–974 consider the proportionate flow shop with a slow bottleneck machine and propose the SLDR heuristic for it. Choi et al. (2007) derive a data-dependent worst-case ratio bound for the SLDR heuristic which is then bounded by two. In this note, we show that the tight worst-case ratio bound of the SLDR heuristic is 3/2.     

A note on the complexity of flow-shop scheduling with deteriorating jobs

This paper is a note on “Complexity analysis of job-shop scheduling with deteriorating jobs” [G. Mosheiov, Complexity analysis of job-shop scheduling with deteriorating jobs, Discrete Applied Mathematics 117 (2002) 195-209]. A proportional deterioration rate is assumed and the objective is the minimization of the makespan. Mosheiov presents NP-hardness results for flow-shops and open-shops with three or more machines and for job-shops with two or more machines. The proof of NP-hardness for the flow-shop case is however not correct. This paper provides a correct proof.     

The hybrid flow shop scheduling problem

The scheduling of flow shops with multiple parallel machines per stage, usually referred to as the hybrid flow shop (HFS), is a complex combinatorial problem encountered in many real world applications. Given its importance and complexity, the HFS problem has been intensively studied. This paper presents a literature review on exact, heuristic and metaheuristic methods that have been proposed for its solution. The paper briefly discusses and reviews several variants of the HFS problem, each in turn considering different assumptions, constraints and objective functions. Research opportunities in HFS are also discussed.     

Two-machine flow shop total tardiness scheduling problem with deteriorating jobs

This paper studies a two-machine scheduling problem with deteriorating jobs which their processing times depend on their waiting time. We develop a branch and bound algorithm to minimize the total tardiness criteria. A lower bound, several dominance properties and an initial upper bound derived from a heuristic algorithm are used to increase the speed of branch and bound algorithm and decrease its required memory space. Computational results are presented to evaluate effectiveness and efficiency of the algorithms.     

Flow shop scheduling with heterogeneous workers

We propose an extension to the flow shop scheduling problem named Heterogeneous Flow Shop Scheduling Problem (Het-FSSP), where two simultaneous issues have to be resolved: finding the best worker assignment to the workstations, and solving the corresponding scheduling problem. This problem is motivated by Sheltered Work centers for Disabled, whose main objective is the labor integration of persons with disabilities, an important aim not only for these centers but for any company desiring to overcome the traditional standardized vision of the workforce. In such a scenario the goal is to maintain high productivity levels by minimizing the maximum completion time, while respecting the diverse capabilities and paces of the heterogeneous workers, which increases the complexity of finding an optimal schedule. We present a mathematical model that extends a flow shop model to admit a heterogeneous worker assignment, and propose a heuristic based on scatter search and path relinking to solve the problem. Computational results show that this approach finds good solutions within a short time, providing the production managers with practical approaches for this combined assignment and scheduling problem.     

Approximating a two-machine flow shop scheduling under discrete scenario uncertainty

This paper deals with the two machine permutation flow shop problem with uncertain data, whose deterministic counterpart is known to be polynomially solvable. In this paper, it is assumed that job processing times are uncertain and they are specified as a discrete scenario set. For this uncertainty representation, the min-max and min-max regret criteria are adopted. The min-max regret version of the problem is known to be weakly NP-hard even for two processing time scenarios. In this paper, it is shown that the min-max and min-max regret versions of the problem are strongly NP-hard even for two scenarios. Furthermore, the min-max version admits a polynomial time approximation scheme if the number of scenarios is constant and it is approximable with performance ratio of 2 and not (4/3 − ?)-approximable for any ? > 0 unless P = NP if the number of scenarios is a part of the input. On the other hand, the min-max regret version is not at all approximable even for two scenarios.     

Approximation algorithms for two-machine flow shop scheduling with batch setup times

In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n logn) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

Approximability of flow shop scheduling

Shop scheduling problems are notorious for their intractability, both in theory and practice. In this paper, we construct a polynomial approximation scheme for the flow shop scheduling problem with an arbitrary fixed number of machines. For the three common shop models (open, flow, and job), this result is the only known approximation scheme. Since none of the three models can be approximated arbitrarily closely in the general case (unless P = NP), the result demonstrates the approximability gap between the models in which the number of machines is fixed, and those in which it is part of the input of the instance. The result can be extended to flow shops with job release dates and delivery times and to flow shops with a fixed number of stages, where the number of machines at any stage is fixed. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.A preliminary version of this paper appeared in theProceedings of the 36th Annual IEEE Symposium on the Foundations of Computer Science, 1995.Research supported by NSF grant DMI-9496153.     

Approximative procedures for no-wait job shop scheduling

In this article we consider the no-wait job shop problem with makespan objective. Based on a decomposition of the problem into a sequencing and a timetabling problem, we propose two local search algorithms. Extensive computational tests in which the algorithms compare favorably to the best existing strategies are reported. Although not specifically designed for that purpose, our algorithms also outperform one of the best no-wait flow shop algorithms in literature.     

Two-machine flow shop scheduling problem with an outsourcing option

We consider a two-machine flow shop problem in which each job is processed through an in-house system or outsourced to a subcontractor. A schedule is established for the in-house jobs, and performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and total outsourcing costs. We show that the problem is NP-hard in the ordinary sense. We consider a special case in which each job has a processing requirement, and each machine a characteristic value. In this case, the time a job occupies a machine is equal to the job’s processing requirement plus a setup time equal to the characteristic value of that machine. We introduce some optimality conditions and present a polynomial-time algorithm to solve the special case.     

Outsourcing and scheduling for two-machine ordered flow shop scheduling problems

This paper considers a two-machine ordered flow shop problem, where each job is processed through the in-house system or outsourced to a subcontractor. For in-house jobs, a schedule is constructed and its performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and the total outsourcing cost. Since this problem is NP-hard, we present an approximation algorithm. Furthermore, we consider three special cases in which job j has a processing time requirement p_j, and machine i a characteristic q_i. The first case assumes the time job j occupies machine i is equal to the processing requirement divided by a characteristic value of machine i, that is, p_j/q_i. The second (third) case assumes that the time job j occupies machine i is equal to the maximum (minimum) of its processing requirement and a characteristic value of the machine, that is, max{p_j, q_i} (min{p_j, q_i}). We show that the first and the second cases are NP-hard and the third case is polynomially solvable.     

Complexity of flow shop scheduling problems with transportation constraints

In most manufacturing and distribution systems, semi-finished jobs are transferred from one processing facility to another by transporters such as Automated Guided Vehicles, robots and conveyors, and finished jobs are delivered to warehouses or customers by vehicles such as trucks.This paper investigates two-machine flow shop scheduling problems taking transportation into account. The finished jobs are transferred from the processing facility and delivered to customers by truck. Both transportation capacity and transportation times are explicitly taken into account in these models. We study the class of flow shop problems by analysing their complexity. For the makespan objective function, we prove that this problem is strongly NP-hard when the capacity of a truck is limited to two or three parts with an unlimited buffer at the output of the each machine. This problem with additional constraints, such as blocking, is also proven to be strongly NP-hard.     

Bounding strategies for the hybrid flow shop scheduling problem

In this paper, we investigate new lower and upper bounds for the multiple-center hybrid flow shop scheduling problem. We propose a family of center-based lower bounds as well as a destructive lower bound that is based on the concept of revised energetic reasoning. Also, we describe an optimization-based heuristic that requires iteratively solving a sequence of parallel machine problems with heads and tails. We present the results of extensive computational experiments that provide evidence that the proposed bounding procedures consistently improve the best existing ones.     

Two-machine flow shop scheduling problems with minimal and maximal delays

In this paper, we show lower bounds and upper bounds for the F2/max delay/Cmax problem. These bounds allow us to build a branch-and-bound procedure. Computational experiments reveal that these bounds and the associated branch-and-bound procedure are efficient. Received: May 2004 / Revised version: February 2005 AMS classification: 90B35, 90C57