Open shop unit-time scheduling problems with symmetric objective functions

The paper addresses the open-shop scheduling problem with unit-time operations and nondecreasing symmetric objective function depending on job completion times. We construct two schedules, one being optimal for any symmetric convex function, the other one for any symmetric concave function. Both schedules are given by analytically defined formulas that determine in O(1) time for each operation the unit-length time slot for its processing.Received: June 2004, Revised: January 2005, AMS classification: 90B35, 68Q25     

Open shop scheduling problem to minimize makespan with release dates

The scheduling problem of open shop to minimize makespan with release dates is investigated in this paper. Unlike the usual researches to confirm the conjecture that the tight worst-case performance ratio of the Dense Schedule (DS) is 2 − 1/m, where m is the number of machines, the asymptotic optimality of the DS is proven when the problem scale tends to infinity. Furthermore, an on-line heuristic based on DS, Dynamic Shortest Processing Time-Dense Schedule, is presented to deal with the off-line and on-line versions of this problem. At the end of the paper, an asymptotically optimal lower bound is provided and the results of numerical experiments show the effectiveness of the heuristic.     

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.     

Open shop scheduling with some additional constraints

An open shop scheduling problem is presented; preemptions during processing of a job on a processorp is allowed but the job cannot be sent on another processorq before it is finished onp. A graph-theoretical model is described and a characterization is given for problems where schedules with such restricted preemptions useT time units whereT is the maximum of the processing times of the jobs and of the working times of the processors. The general case is shown to be NP-complete. We also consider the case where some constraints of simultaneity are present. Complexity of the problem is discussed and a solvable case is described.     

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.     

Nonpreemptive open shop with restricted processing times

A polynomial time algorithm was given by Fiala for the nonpreemptivem-processor open shop problem whenever the sum of processing times for one processor is large enough with respect to the maximal processing time. Here a special case where all processing times are from a bounded cardinality set of nonnegative integers is studied. For such a situation we give anO(nm) algorithm while the algorithm of Fiala works inO(n ² m ³) wheren is the number of jobs.     

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.     

A new heuristic for open shop total completion time problem

The m  -machine open shop problem to minimize the sum of the completion times is investigated in our paper. First, a heuristic algorithm, Shortest Processing Time Block, is presented to deal with problem _Om|n=km|∑_Cj$O_m|n=\mathit{km}|\sum C_j$, where k   is positive integer. And then, the heuristic is extended to solve the general problem _Om‖∑_Cj$O_m\Vert \sum C_j$. It is proved that the heuristic is asymptotically optimal when the job number goes to infinity. At the end of this paper, numerical experimentation results show the effectiveness of the heuristic algorithm.     

Parallel variable neighbourhood search algorithms for job shop scheduling problems

^** Email: msevkli{at}fatih.edu.tr^*** Corresponding author. Email: mehmetaydin{at}acm.org, mehmet.aydin{at}beds.ac.uk Variable neighbourhood search (VNS) is one of the most recentmetaheuristics used for solving combinatorial optimization problemsin which a systematic change of neighbourhood with a local searchis carried out. However, as happens with other metaheuristics,it takes a long time to reach some useful solutions while solvingsome sort of hard combinatorial problems such as job shop scheduling(JSS). Parallelization is one of the most considerable policiesto overcome this matter. In this paper, firstly, a number ofVNS algorithms are examined for JSS problems and then four differentparallelization policies are taken into account to determineefficient parallelization for VNS algorithms. The experimentationreveals the performance of various VNS algorithms and the efficiencyof policies to follow in parallelization. In the end, the unilateral-ringtopology, a noncentral parallelization method, is found as themost efficient policy.     

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.     

Asymptotically optimal schedules for single-server flow shop problems with setup costs and times

We consider the processing of M jobs in a flow shop with N stations in which only a single server is in charge of all stations. We demonstrate that for the objective of minimizing the total setup and holding cost, a class of easily implementable schedules is asymptotically optimal.     

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.     

Cyclic job shop scheduling problems with blocking

A tabu search algorithm for a cyclic job shop problem with blocking is presented. Operations are blocking if they must stay on a machine after finishing when the next machine is occupied by another job. During this stay the machine is blocked for other jobs. For this problem traditional tabu search moves often lead to infeasible solutions. Recovering procedures are developed which construct nearby feasible solutions. Computational results are presented for the approach.     

The two-machine open shop problem: To fit or not to fit, that is the question

We consider the open shop scheduling problem with two machines. Each job consists of two operations, and it is prescribed that the first (second) operation has to be executed by the first (second) machine. The order in which the two operations are scheduled is not fixed, but their execution intervals cannot overlap. We are interested in the question whether, for two given values D₁ and D₂, there exists a feasible schedule such that the first and second machine process all jobs during the intervals [0,D₁] and [0,D₂], respectively.We formulate four simple conditions on D₁ and D₂, which can be verified in linear time. These conditions are necessary and sufficient for the existence of a feasible schedule. The proof of sufficiency is algorithmical, and yields a feasible schedule in linear time. Furthermore, we show that there are at most two non-dominated points (D₁,D₂) for which there exists a feasible schedule.     

A polynomial time algorithm for a chance-constrained single machine scheduling problem

This paper gives an O(n√nlog³n) time algorithm for the chance-constrained sequencing problem on a single machine, where n is the number of jobs and the objective is to minimize the number of jobs which are early with probability not smaller than α (a given constant) against the common due time d.     

Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance

This paper deals with a single machine scheduling problems with availability constraints. The unavailability of machine results from periodic maintenance activities. In our research, a periodic maintenance consists of several maintenance periods. We consider a machine should stop to maintain after a periodic time interval or to change tools after a fixed amount of jobs processed simultaneously. Each maintenance period is scheduled after a periodic time interval. We study the problems under deterministic environment and flexible maintenance considerations. Preemptive operation is not allowed. In addition, we propose a more reasonable flexible model for the real production settings. The objective is to minimize the makespan. The proposed problem is NP-hard in the strong sense and some heuristic algorithms are provided. The purpose is to present an efficient and effective heuristic algorithm so that it will be straightforward and easy to implement. Computational results show that the proposed algorithm first fit decreasing (DFF) performs well.     

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     

Maximum-cover source location problems with objective edge-connectivity three

Given a graph G = (V, E), a set of vertices covers a vertex if the edge-connectivity between S and v is at least a given number k. Vertices in S are called sources. The maximum-cover source location problem, which is a variation of the source location problem, is to find a source set S with a given size at most p, maximizing the sum of the weight of vertices covered by S. In this paper, we show a polynomial-time algorithm for this problem in the case of k = 3 for a given undirected graph with a vertex weight function and an edge capacity function. Moreover, we show that this problem is NP-hard even if vertex weights and edge capacities are both uniform for general k.