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.     

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.     

Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function

The paper present a linear-time algorithm for solving the two machine open shop scheduling problem to minimize an arbitrary regular penalty function depending on the lengths of periods during which the machines are used. Both the preemptive and the nonpreemptive cases of the problem are considered.     

On-line two-machine open shop scheduling with time lags

We analyze the performance of the greedy algorithm for the on-line two-machine open shop scheduling problem of minimizing makespan, in which time lags exist between the completion time of the first and the start time of the second operation of any job. The competitive ratio for the greedy algorithm is 2, and it can be reduced to 5/3 if the maximum time lag is less than the minimum positive processing time of any operation. These ratios are tight. We also prove that no on-line non-delay algorithm can have a better competitive ratio.     

Two-machine open shop scheduling with special transportation times

The paper considers a problem of scheduling n jobs in a two-machine open shop to minimise the makespan, provided that preemption is not allowed and the interstage transportation times are involved. In general, this problem is known to be NP-hard. We present a linear time algorithm that finds an optimal schedule if no transportation time exceeds the smallest of the processing times. We also describe an algorithm that creates a heuristic solution to the problem with job-independent transportation times. Our algorithm provides a worst-case performance ratio of 8/5 if the transportation time of a job depends on the assigned processing route. The ratio reduces to 3/2 if all transportation times are equal.     

Two-machine flow shop no-wait scheduling with machine maintenance

We study a two-machine flow shop scheduling problem with no-wait in process, in which one of the machines is subject to mandatory maintenance. The length of the maintenance period is defined by a non-decreasing function that depends on the starting time of that maintenance. The objective is to minimize the completion time of all activities. We present a polynomial-time approximation scheme for this problem. Received: November 2004 / Received version: March 2005 AMS classification: 90B35, 90B30, 90C59 The research was partly supported by INTAS (Project 03-51-5501) All correspondence to: Vitali A. Strusevich     

Minimizing makespan in a two-stage hybrid flow shop scheduling problem with open shop in one stage

This paper considers a scheduling problem in two-stage hybrid flow shop, where the first stage consists of two machines formed an open shop and the other stage has only one machine. The objective is to minimize the makespan, i.e., the maximum completion time of all jobs. We first show the problem is NP-hard in the strong sense, then we present two heuristics to solve the problem. Computational experiments show that the combined algorithm of the two heuristics performs well on randomly generated problem instances.     

Two-stage flexible flow shop scheduling subject to fixed job sequences

This paper investigates the scheduling problem in a two-stage flexible flow shop, which consists of m stage-1 parallel dedicated machines and a stage-2 bottleneck machine, subject to the condition that n _l jobs per type l∈{1, …, m} are processed in a fixed sequence. Four regular performance metrics, including the total completion time, the maximum lateness, the total tardiness, and the number of tardy jobs, are considered. For each considered objective function, we aim to determine an optimal interleaving processing sequence of all jobs coupled with their starting times on the stage-2 bottleneck machine. The problem under study is proved to be strongly NP-hard. An O(m²Π_l=1 ^m n _l ²) dynamic programming algorithm coupled with numerical experiments is presented.     

The equal allocation policy in open shop batch scheduling

We study the optimality of the very practical policy of equal allocation of jobs to batches in batch scheduling problems on an m-machine open shop. The objective is minimum makespan. We assume unit processing time jobs, machine-dependent setup times and batch availability. We show that equal allocation is optimal for a two-machine and a three-machine open shop. Although, this policy is not necessarily optimal for larger size open shops, it is shown numerically to produce very close-to-optimal schedules.     

A projective algorithm for preemptive open shop scheduling with two multiprocessor groups

We study a multiprocessor extension of the preemptive open shop scheduling problem, where the set of processors is partitioned into processor groups. We show that the makespan minimization problem is polynomially solvable for two multiprocessor groups even if preemptions are restricted to integral times.     

A tabu search approach for proportionate multiprocessor open shop scheduling

In the multiprocessor open shop scheduling problem, jobs are to be processed on a set of processing centers—each having one or more parallel identical machines, while jobs do not have a pre-specified obligatory route. A special case is the proportionate multiprocessor open shop scheduling problem (PMOSP) in which the processing time on a given center is not job-dependent. Applications of the PMOSP are evident in health care systems, maintenance and repair shops, and quality auditing and final inspection operations in industry. In this paper, a tabu search (TS) approach is presented for solving the PMOSP with the objective of minimizing the makespan. The TS approach utilizes a neighborhood search function that is defined over a network representation of feasible solutions. A set of 100 benchmark problems from the literature is used to evaluate the performance of the developed approach. Experimentations show that the developed approach outperforms a previously developed genetic algorithm as it produces solutions with an average of less than 5 % deviation from a lower bound, and 40 % of its solutions are provably optimal.     

A dynamic programming algorithm for scheduling jobs in a two-machine open shop with an availability constraint

This paper studies a two-machine open shop scheduling problem with an availability constraint, ie we assume that a machine is not always available and that the processing of the interrupted job can be resumed when the machine becomes available again. We consider the makespan minimization as criterion. This problem is NP-hard. We develop a pseudo-polynomial time dynamic programming algorithm to solve the problem optimally when the machine is not available at time s>0. Then, we propose a mixed integer linear programming formulation, that allows to solve instances with up to 500 jobs optimally in less than 5?min with CPLEX solver. Finally, we show that any heuristic algorithm has a worst-case error bound of 1.     

Multi-objective open shop scheduling by considering human error and preventive maintenance

This study presents an open shop scheduling model by considering human error and preventive maintenance. The proposed mathematical model takes into account conflicting objective functions including makespan, human error and machine availability. In order to find the optimum scheduling, human error, maintenance and production factors are considered, simultaneously. Human error is measured by Human Error Assessment and Reduction Technique (HEART). Three metaheuristic methods including non-dominated sorting genetic algorithm-II (NSGA-II), multi-objective particle swarm optimization (MOPSO) and strength Pareto evolutionary algorithm II (SPEA-II) are developed to find near-optimal solution. The Taguchi method is applied by adjusting parameters of metaheuristic algorithms. Several illustrative examples and a real case study (auto spare parts manufacturer) are applied to show the applicability of the multi-objective mixed integer nonlinear programming model. The proposed approach of this study may be used for similar open shop problems with minor modifications.     

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.     

Flexible job shop scheduling problem for parallel batch processing machine with compatible job families

Flexible Job-Shop Scheduling Problem (FJSP) with Parallel Batch processing Machine (PBM) is studied. First, a Mixed Integer Programming (MIP) formulation is proposed for the first time. In order to address an NP-hard structure of this problem, the formulation is modified to selectively schedule jobs. Although there are many jobs on a given floor, semiconductor manufacturing is most challenged by priority jobs that promise a significant amount of financial compensation in exchange for an expedited delivery. This modification could leave some non-priority jobs unscheduled. However, it vastly expedites the discovery of improving solutions by first branching on integer variables with higher priority jobs. This study then turns job-dependent processing times into job-independent ones by assuming a machine has an equal processing time on different jobs. This assumption is roughly true or acceptable for the sake of the reduced computational time in the industry. These changes significantly reduce computational time compared to the original model when tested on a set of common problem instances from the literature. Computational results show that this proposed model can generate an effective schedule for large problems. Author encourages other researchers to propose an improved MIP model.     

An optimal online algorithm for two-machine open shop preemptive scheduling with bounded processing times

This paper deals with a two-machine open shop scheduling problem. The objective is to minimize the makespan. Jobs arrive over time. We study preemption-resume model, i.e., the currently processed job may be preempted at any moment in necessary and be resumed some time later. Let p _{1, j} and p _{2, j} denote the processing time of a job J _j on the two machines M ₁ and M ₂, respectively. Bounded processing times mean that 1 ≤ p _{i, j}  ≤ α (i = 1, 2) for each job J _j , where α ≥ 1 is a constant number. We propose an optimal online algorithm with a competitive ratio ${\frac{5\alpha-1}{4\alpha}}$ .     

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.     

Multi-resource shop scheduling with resource flexibility

The shop scheduling problem tackled in this paper integrates many features that can be found in practical settings. Every operation may need several resources to be performed, and furthermore, a resource may be selected in a given set of candidates resources. Finally, we also consider that an operation may have more than one predecessor and/or more than one successor on the routing. The problem is then to both assign operations to resources and sequence operations on the resources, in order to minimize the maximum completion time. A disjunctive graph representation of this problem is presented and a connected neighborhood structure is proposed. The latter can be used to derive a local search algorithm such as tabu search. Finally, some numerical experiments are presented and discussed.     

Job shop scheduling with beam search

Beam Search is a heuristic method for solving optimization problems. It is an adaptation of the branch and bound method in which only some nodes are evaluated in the search tree. At any level, only the promising nodes are kept for further branching and remaining nodes are pruned off permanently. In this paper, we develop a beam search based scheduling algorithm for the job shop problem. Both the makespan and mean tardiness are used as the performance measures. The proposed algorithm is also compared with other well known search methods and dispatching rules for a wide variety of problems. The results indicate that the beam search technique is a very competitive and promising tool which deserves further research in the scheduling literature.