Search

This paper deals with the problem of scheduling a set of unit‐time jobs on a set of uniform machines. The jobs are subject to conflict constraints modeled by a graph G called the conflict graph, in which adjacent jobs cannot be processed on a same machine. The objective considered herein is the minimization of maximum job completion time in the schedule, which is famous to be NP‐hard in the strong sense. The first part of this paper is an extensive study of the computational complexity of the problem restricted to several graph classes, namely: split graphs, interval graphs, forests, trees, paths and cycles. Afterward, we focus on the resolution of the problem with arbitrary conflict graphs. For this latter, a combination of a mixed integer linear programming (MILP) formulation, lower and upper bounds is proposed. A wild range of computational experiments proved the efficiency of this technique to tremendously reduce runtime and produce more optimal solutions (around 80% in average). Furthermore, a deep analysis of the resolution process based on both the density of the conflict graph as well as machine speeds (including identical machines) is thoroughly reported. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We address in this paper the two-machine job shop scheduling problem with a single server that sets up the jobs before they get processed on the machines. The server is only needed during the set-up and becomes free at the end of this phase. Moreover, the set-ups are non-anticipatory and the set-up times are sequence-independent. We seek a schedule that minimizes the overall completion time, also called the makespan. We propose several lower bounds to the problem and prove the N P -hardness in the strong sense of two restricted cases. In addition, we present a linear time algorithm for a special case. In order to solve the general problem, we develop a genetic and simulated annealing algorithms that use feasibility guaranteed procedures. An experimental study is carried out to analyze the performance of these meta-heuristic methods. [ABSTRACT FROM AUTHOR]

The two-machine chain-reentrant shop scheduling with the objective of minimizing the makespan, assumes that the tasks pass from the first machine to the second and return back to the first machine. In this paper, we consider the same problem in which an exact time lag between the two operations on the first machine is imposed. In Amrouche and Boudhar (2016) the authors proved that this problem is NP-hard in the strong sense in the case of identical time lags. We propose heuristic algorithms with empirical results for the latter. In addition, we establish a new NP-hardness result and some polynomial cases. [ABSTRACT FROM PUBLISHER]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 Scheduling problem with agreement graph on two identical machines is NP-hard for trees. • The Scheduling problem with agreement graph on two identical machines is solvable in polynomial time for caterpillars. • The Scheduling problem with agreement graph on two identical machines is solvable in polynomial time for cycles. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 M1,M2,M1 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

• Schedule a set of jobs on a two-machine open shop environment with a single server. • The server is required to perform non-anticipatory and sequence-independent set-ups on the jobs before their processing on the machines. • Three restricted versions of the corresponding decision problem are NP-hard in the strong sense. • Exhibition of a polynomial time algorithm for a special case. • Design of serval heuristic and a hyper-heuristic algorithms, along with an extensive simulation. We address in this paper the two-machine open shop problem with set-up time considerations to build schedules that minimize the overall completion time, known as the makespan. In the model we are considering, the set-up, handled by a single server, consists of a preparation phase separated from the processing phase. Once the server completes the preparation of a job, it becomes again available for setting up other jobs, leaving the current one to complete its processing. We prove several NP -completeness results, exhibit a linear time algorithm for a special case, and develop heuristic and hyper-heuristic algorithms to solve the general problem along with an experimental study. [ABSTRACT FROM AUTHOR]