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.     

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.     

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.     

The two-machine no-wait general and proportionate open shop makespan problem

We consider the two-machine no-wait open shop minimum makespan problem in which the determination of an optimal solution requires an optimal pairing of the jobs followed by the optimal sequencing of the job pairs. We show that the required enumeration can be curtailed by reducing the pair sequencing problem for a given pair set to a traveling salesman problem which is equivalent to a two-machine no-wait flow shop problem solvable in O(n log n) time. We then propose an optimal O(n log n) algorithm for the proportionate problem with equal machine speeds in which each job has the same processing time on both machines. We show that our O(n log n) algorithm also applies to the more general proportionate problem with equal machine speeds and machine-specific setup times. We also analyze the proportionate problem with unequal machine speeds and conclude that the required enumeration can be further curtailed (compared to the problem with arbitrary job processing times) by eliminating certain job pairs from consideration.     

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.     

Solving the serial batching problem in job shop manufacturing systems

This paper addresses the serial batch scheduling problem embedded in a job shop environment to minimize makespan. Sequence dependent family setup times and a job availability assumption are also taken into account. In consideration of batching decisions, we propose a tabu search algorithm which consists of various neighborhood functions, multiple tabu lists and a sophisticated diversification structure. Computational experiments show that our algorithm outperforms a well-known tabu search approach which is developed for solving the traditional job shop problem. These results also confirm the benefits of batching.     

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.     

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-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.     

Computing lower and upper bounds for a large-scale industrial job shop scheduling problem

In this paper we present a case study from the lighting industry concerned with the scheduling of a set of job families each representing the production of a particular end-item in a given quantity. It is a job shop type problem, where each job family has a number of routing alternatives, and the solution has to respect batching and machine availability constraints. All jobs of the same job family have a common release date and a common due date, and they differ only in size. The objective is to minimize the total tardiness of the job families, rather than that of individual jobs. We propose a two-phase method based on solving a mixed-integer linear program and then improving the initial solution by tabu search. We evaluate our method on real-world as well as generated instances.     

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 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.     

On-line scheduling of small open shops

We investigate the problem of on-line scheduling open shops of two and three machines with an objective of minimizing the schedule makespan. We first propose a 1.848-competitive permutation algorithm for the non-preemptive scheduling problem of two machines and show that no permutation algorithm can be better than 1.754-competitive. Secondly, we develop a (27/19)-competitive algorithm for the preemptive scheduling problem of three machines, which is most competitive.     

A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem

This paper deals with a general job shop scheduling problem with multiple constraints, coming from printing and boarding industry. The objective is the minimization of two criteria, the makespan and the maximum lateness, and we are interested in finding an approximation of the Pareto frontier. We propose a fast and elitist genetic algorithm based on NSGA-II for solving the problem. The initial population of this algorithm is either randomly generated or partially generated by using a tabu search algorithm, that minimizes a linear combination of the two criteria. Both the genetic and the tabu search algorithms are tested on benchmark instances from flexible job shop literature and computational results show the interest of both methods to obtain an efficient and effective resolution method.     

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 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.     

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.     

Fuzzy job shop scheduling with lot-sizing

This paper deals with a problem of determining lot-sizes of jobs in a real-world job shop-scheduling in the presence of uncertainty. The main issue discussed in this paper is lot-sizing of jobs. A fuzzy rule-based system is developed which determines the size of lots using the following premise variables: size of the job, the static slack of the job, workload on the shop floor, and the priority of the job. Both premise and conclusion variables are modelled as linguistic variables represented by using fuzzy sets (apart from the priority of the job which is a crisp value). The determined lots’ sizes are input to a fuzzy multi-objective genetic algorithm for job shop scheduling. Imprecise jobs’ processing times and due dates are modelled by using fuzzy sets. The objectives that are used to measure the quality of the generated schedules are average weighted tardiness of jobs, the number of tardy jobs, the total setup time, the total idle time of machines and the total flow time of jobs. The developed algorithm is analysed on real-world data obtained from a printing company.     

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.