Search

In this paper, we study the two-machine no-wait flow shop scheduling problem with two competing agents. The objective is to minimize the overall completion time of one agent subject to an upper bound on the makespan of the second agent. We proved the $$\mathcal {NP}$$ -hardness for three special cases: (1) each agent has exactly two operations. (2) the jobs of one agent require processing only on one machine, (3) the no-wait constraint is only required for the jobs of one agent. We exhibited polynomial time algorithms for other restricted cases. We also proposed a mathematical programming model and a branch and bound scheme as solving approaches for small-scale problems. For large instances, we present a tabu search meta-heuristic algorithm. An intensive experimental study is conducted to illustrate the effectiveness of the proposed exact and approximation algorithms.

This paper addresses the problem of scheduling n identical jobs on a set of m parallel uniform machines. The jobs are subjected to conflicting constraints modelled by an undirected graph G, in which adjacent jobs are not allowed to be processed on the same machine. Minimising the maximum completion time in the schedule (makespan Cmax) is known to be NP-hard. We prove that when G is restricted to complete bipartite graphs the problem remains NP-hard for arbitrary number of machines, however, if m is fixed an optimal solution can be obtained in polynomial time. To solve the general case of the problem, we propose mixed-integer linear programming (MILP) formulations alongside with lower bounds and heuristic approaches. Furthermore, computational experiments are carried out to measure the performance of the proposed methods.

Scheduling problem with agreement graph on two identical machines is addressed. The problem consists in scheduling a set of non-preemptive jobs on two identical machines in a minimum time. Agreement constraints are imposed over the jobs. They express that only specific jobs can be scheduled concurrently on different machines. These constraints are represented by an agreement graph. This problem can be seen as a problem of partitioning a vertex-weighted graph into cliques. The problem is NP-hard for an arbitrary agreement graph, but for some particular graphs the problem is still open. For this reason, we study the complexity of the problem for some specific graphs. In particular, we prove the NP-hardness of the problem if the agreement graph is a tree. We also propose polynomial time algorithms to solve the problem for the cases of caterpillars and cycles.

The problem of scheduling n unit-time jobs on m uniform machines is raised in this paper. The jobs are subject to conflicting constraints modeled by a graph G, called the conflict graph. Adjacent jobs (conflicting jobs) in G are not allowed to be processed on a same machine. The addressed objective is the minimization of the makespan of the schedule, which is known to be strongly NP-hard in the literature. The contribution of the current paper is an unorthodox branch-and-bound algorithm that proved to be highly efficient through empirical testing.

With ever-increasing concerns about climate change, and in the context of diminishing fossil energy resources, energy consumption has become a subject of great importance. In this framework, our study is concerned with the reduction of the energy consumed by a manufacturing system composed of several unrelated parallel machines. We investigate the problem of scheduling a set of n deteriorating jobs on m parallel unrelated machines subject to a deterioration effect, where the processing time of each job is a linear deterioration function of the starting time. The objective is to determine the best scheduling of the jobs, minimizing the makespan and the total energy consumption. We implement a nondominated sorting-based multiobjective algorithm (NSGA-II)-based approaches with a given scheduling rules to solve the developed mathematical model of the considered problem. The performance of the proposed approaches are compared with an exact algorithm and evaluated through computational experiments. Then, we give a multiobjective decision-making method based on the TOPSIS (technique for order of preference by similarity to ideal solution) technique to determine the best solution from the Pareto front according to the decision-maker’s preferences.

This paper deals with open shops subject to the constraint that some conflicting jobs cannot be processed simultaneously on different machines. In the context of our study, these conflicts are given by an undirected graph, called the conflict graph. We seek a schedule that minimizes the maximum completion time (makespan). We first prove the NP-hardness of different versions of this problem. Then, we present polynomial-time solvable cases, for which we devise simple and efficient algorithms. On the other hand, we present heuristics and lower bounds for the general case. The heuristics are based on the construction of matchings in bipartite graphs as well as on a specific insertion technique combined with beam search. Finally, we test the efficiency of the heuristics and report our computational experiments that display satisfying results.

This paper addresses the problem of scheduling jobs on flow shops subject to constraints given by an undirected graph, in which each edge joins a pair of conflicting jobs that cannot be processed simultaneously on different machines. We first show that the problem of minimizing the maximum completion time (makespan) is NP-hard for several versions. Then, we present polynomial-time solvable cases. On the other hand, we propose heuristic approaches and lower bounds alongside with an experimental study.

PurposeThis paper studies the preemptive scheduling problem of independent jobs on identical machines. The purpose of this paper is to minimize the makespan under the imposed constraints, namely, the ones that relate the transportation delays which are required to transport a preempted job from one machine to another. This study considers the case when the transportation delays are variable.Design/methodology/approachThe contribution is twofold. First, this study proposes a new linear programming formulation in real and binary decision variables. Then, this study proposes and implements a solution strategy, which consists of two stages. The goal of the first stage is to obtain the best machines order using a local search strategy. For the second stage, the objective is to determine the best possible sequence of jobs. To solve the preemptive scheduling problem with transportation delays, this study proposes a heuristic and two metaheuristics (simulated annealing and variable neighborhood search), each with two modes of evaluation.FindingsComputational experiments are presented and discussed on randomly generated instances.Practical implicationsThe study has implications in various industrial environments when the preemption of jobs is allowed.Originality/valueThis study proposes a new linear programming formulation for the problem with variable transportation delays as well as a corresponding heuristic and metaheuristics.

International audience; This paper addresses the problem of scheduling jobs on a two-machine open shop subject to constraints given by an agreement graph G, such that jobs can be processed simultaneously on different machines if and only if they are represented by adjacent vertices in G. The problem of minimizing the maximum completion time (makespan) is strongly NP-hard for three distinct values of processing times and for G being a bipartite graph. We extend the study presented in [3] and [4] to the proportionate open shop system. We first prove the NP-hardness of the case of two values of processing times and more general agreement graphs which closes definitely the complexity status of the problem. Then, we present some restricted cases that can be solved in polynomial time. We also derive new complexity results of the open shop under resource constraints and of the partition into triangles problem.

International audience; This paper addresses a generalization of the coupled-operations scheduling problem in the context of a flow shop environment. We consider the two-machine scheduling problem with the objective of minimizing the makespan. Each job consists of a coupled-operation to be processed first on the first machine and a single operation to be then processed on the second machine. A coupled-operation contains two operations separated by an exact time delay. The single operation can start on the second machine only when the coupled-operation on the first machine is completed. We prove the NP-completeness of two restricted versions of the general problem, whereas we also exhibit several other well solvable cases.

This paper addresses the problem of scheduling, on a two-machine flow shop, a set of unit-time operations subject to the constraints that some conflicting jobs cannot be scheduled simultaneously on different machines. In the context of our study, these conflicts are modelled by general graphs. The problem of minimising the maximum completion time (makespan) is known to be NP-hard in the strong sense. We propose a mixed-integer linear programming (MILP) model. Then, we develop a branch and bound algorithm based on new lower and upper bound procedures. We further provide a computer simulation to measure the performance of the proposed approaches. The computational results show that the branch and bound algorithm outperforms the MILP model and can solve instances of size up to 20,000 jobs.

This paper considers a reentrant flow shop with two machines and exact time lag L , in which each task may be processed in this order M 1 , M 2 , M 1 and there is an identical time lag between the completion time of the first operation and the start time of the second operation on the first machine. The objective is to minimize the total completion time. We prove the NP-hardness of a special case and we give some special subproblems that can be solved in polynomial time.

In this paper, we consider the problem of scheduling jobs on a two-machine flow shop subject to constraints represented by an undirected graph G, in which each edge joins a pair of conflicting jobs that cannot be processed simultaneously on different machines. The problem of minimizing the maximum completion time (makespan) is known to be NP-hard in the strong sense even when all the operations require one unit of processing time. We prove that the permutation schedules are not dominant even for two machines, and we present a special case for which an optimal schedule can be found by a permutation schedule. On the other hand, we propose four Mixed Integer Linear Programming (MILP) models alongside with an experimental study to measure their performance on a wide range of test problems.

In this paper, the problem of scheduling with agreements (SWA) is considered. In scheduling, this consists of a set of jobs non-preemptively on identical machines subject to constraints that only some specific jobs can be scheduled concurrently on different machines. These constraints are given by an agreement graph and the aim is to minimise the makespan. In the case of two machines we extend two NP-hardness results of SWA with processing times at most three that hold for bipartite agreement graphs to more general agreement graphs. Complexity results of SWA are established in the case of split and complement of bipartite graphs. We also present some approximation results for SWA.

This paper addresses the chain-reentrant flow shop scheduling problem with two machines and n non-preemptive jobs in the presence of the no-wait constraint; we assume that each job passes from the first machine to the second and returns back to the first machine. The objective is to minimise the makespan. The general problem is NP-hard in the strong sense. Based on a dynamic programming algorithm, we prove that the problem is polynomially solvable when the execution order of the jobs through the machines is a fixed permutation. For the resolution of the general problem, we propose a linear mathematical model, local search heuristics, a simulated annealing metaheuristic and lower bounds with numerical experiments. [Received: 8 February 2019; Revised: 19 June 2019; Revised: 26 August 2019; Revised: 8 October 2019; Revised: 9 November 2019; Accepted: 11 November 2019]

This paper deals with the no-wait job shop scheduling problem resolution. The problem is to find a schedule to minimize the makespan ($$C_{max}$$Cmax), that is, the total completeness time of all jobs. The no-wait constraint occurs when two consecutive operations in a job must be processed without any waiting time either on or between machines. For this, we have proposed two different resolution methods, the first is an exact method based on the branch-and-bound algorithm, in which we have defined a new technique of branching. The second is a particular swarm optimization (PSO) algorithm, extended from the discrete version of PSO. In the proposed algorithm, we have defined the particle and the velocity structures, and an efficient approach is developed to move a particle to the new position. Moreover, we have adapted the timetabling procedure to find a good solution while respecting the no-wait constraint. Using the PSO method, we have reached good results compared to those in the literature.

We consider a chain reentrant shop problem with m machines, in which a no-wait constraint is imposed. Each job goes through m machines in a fixed order and return back to the first machine for its last operation. We seek to minimize the overall finish time (makespan). We first proof some new NP-hard problems in the case of two machines. For the resolution of the general problem we propose a genetic algorithm with numerical experiments.

International audience; The two-machine chain-reentrant shop scheduling with the objective of minimizing the makespan, assumes that the taskspass from the first machine to the second and return back to the first machine. In this paper, we consider the same problem inwhich an exact time lag between the two operations on the first machine is imposed. In Amrouche and Boudhar (2016) theauthors proved that this problem is NP-hard in the strong sense in the case of identical time lags l j = L. We propose heuristicalgorithms with empirical results for the latter. In addition, we establish a new NP-hardness result and some polynomialcases.

International audience; This paper deals with an identical parallel machines scheduling problem, where independent jobs can be preempted and transported from one machine to another. The transportation of a preempted job requires a time called the transportation delay. The goal is to find a solution that minimizes the total completion time (makespan). We first study the case of equal-size jobs where new complexity results are given. Then, to solve the problem with two identical machines, we present a dynamic programming algorithm and a fully polynomial time approximation scheme (FPTAS). Experimental results show the efficiency of the FPTAS compared to a previously published heuristic.

We consider the following problem of scheduling with agreements: a set of jobs must be scheduled non-preemptively on identical machines subject to constraints that only some specific jobs can be scheduled concurrently on different machines. These constraints are represented by an agreement graph and the aim is to minimize the makespan. This problem is NP-hard. We study the complexity of the problem for two machines and arbitrary bipartite agreement graphs, in particular we prove the NP-hardness of the open problem proposed in the literature which is the case of two machines with processing times at most 3. We propose list algorithms with empirical results for the problem in the general case.

In this paper, we present two scheduling hybrid flow shop problems to minimize the makespan. In each problem, we have two stages. In the first problem, one machine at each stage is considered with recirculation of jobs in the second stage (machine). We prove that this first problem is polynomial and we present an algorithm for its resolution. The second problem consists of one machine in the first stage and two identical parallel machines in the second. Jobs can be recirculated a fixed number of times in the second stage. We show that the problem is NP-hard and a polynomial subproblem is proposed. Linear program and heuristics are also presented with numerical experimentations.

In this paper, we consider the problem of scheduling n independent jobs preemptively on m identical parallel machines, to minimize the total completion time (makespan). Each job J"i (i=1,n@?) has a processing time p"i and the transportation of an interrupted job from a machine M"j to another machine M"j"^"' requires d"j"j"^"' units of time. We propose a linear programming formulation in real and binary decision variables and we prove that the problem is NP-hard. Some subproblems are analyzed and solved by polynomial algorithms. Finally we present some heuristics and give some lower bounds of the makespan.

We consider the problem of minimizing the makespan on a batch processing machine, in which jobs are not all compatible. Only compatible jobs can be included into the same batch. This relation of compatibility is represented by a split graph. All jobs are available at the same date. The capacity of the batch processing machine is finite or infinite. The processing time of a batch is given by the processing time of the longest job in the batch. We establish the NP-hardness of the general problem and present polynomial algorithms for several special cases.

We consider the problem of minimizing the makespan on a batch processing machine, in which jobs are not all compatible. Only compatible jobs can be included into the same batch. This relation of compatibility is represented by a split graph. Jobs have release dates. The capacity of the batch processing machine is finite or infinite. The processing time of a batch is given by the processing time of the longest job in the batch. We establish the NP-hardness of the general problem and present polynomial algorithms for several special cases. Relating scheduling theory and graph theory appears to be an interesting and important concept.

International audience; In this paper, we consider the problem of scheduling a set of n jobs on two identical machines with preparation constraints. Each job requires before its execution a set of resources and a non-negligible preparation time. The objective is to minimise the makespan. This problem is NP-hard. We prove the NP-hardness of two specific cases where in the first case preparation times take only three values, whereas in the second case preparation times and the release dates take only two values, respectively. Then, we present some special cases and heuristic algorithms along with an experimental study.

We consider the problem of minimizing the makespan on batch processing machines, in which jobs are not all compatible, i.e. there are at least two jobs that can not be processed simultaneously in the same batch. Each job has a processing time and the capacity of batch processing machines can be finite or infinite. The processing time of a batch is given by the processing time of the longest job in the batch. We prove the NP-hardness of the general problem and present heuristics and exact algorithms for its solution.

In this paper, we deal with the resolution of the scheduling problem with blocking which is known to be non-polynomial-hard. The nature of the workshop defines the type of issue to treat: flow shop problem and job shop problem (JSP). A lot of researches are dedicated in the literature to the resolution of the flow shop problem, whereas not enough works are found concerning JSP. We have oriented our efforts in this paper to the resolution of JSP with blocking. For that, we propose three methods: a parallel version of a branch-and-bound method based on an implicit enumeration, a sequential particle swarm optimisation (PSO) and a parallel PSO. The first one is an exact method but the complexity of the problem makes it useless for more than 10 jobs × 10 machines. For that, we investigate in meta-heuristics which procure good scheduling in real time. A comparison of these methods is presented at the end of this paper.

In this paper, we study the job shop scheduling problem with blocking where the objective is to minimise the maximum completion time (i.e. makespan). To solve this non-polynomial-hard problem, we propose three algorithms. First, we propose a combination of a branch and bound algorithm with alternative graphs. We investigate the performance of this proposal to get an optimal solution in a reasonable time. Next, we develop two methods based on genetic algorithms (GAs): sequential and parallel GAs. In the former, we propose two different ways to encode the individuals: binary code using alternative arcs and priority rules code. In the latter, we propose a parallelisation of the GA, where the master computer is dedicated to the steps of selection, crossover and mutation, and the other computers (slaves) are concerned with the computation of the individual’s fitness. At the end of this paper, we discuss the different results.

In the present study, we consider a special case of multi-purpose machines (MPMs) in which there is a linear order given for the machines. In addition, for each job Ji(1≤i≤n), a 'first permissible' machine hi (1≤h(i)≤m) is given on which it can be processed. Thus, machines Mhi,…, Mm are capable of processing job Ji while machines M1,…, Mhi−1 cannot process job Ji. Each job Ji requires a time pi and the goal is to minimise the makespan. We prove the NP-hardness of the general problem and present some polynomial sub-problems. Heuristics with an exact algorithm of branch and bound type are also presented with numerical experimentations.

In this paper, we aim at compiling the bibliography and the recent developments on scheduling problems involving undirected graphs. Two types of problems are considered: the mutual exclusion scheduling and the scheduling with batch-compatible jobs. We first consider the scheduling problems that can be solved by creating an undirected graph with a vertex for each job and an edge between every pair of conflicting jobs. Then, we consider the problem of minimising the makespan on a batch processing machine in which jobs are not at all compatible. This relation of compatibility is represented by an undirected graph called 'compatibility graph'.