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.

In this study, the potential of phenological indicators derived from Sentinel-2A (S2) time series were evaluated to explore the key variables that allow identifying both cropland and crop types. Ba...

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.

Crop type mapping provides essential information to control and make decisions related to agricultural practices and their regulations. To map crop types accurately, it is important to capture their phenological stages and fine spatial details, especially in a temporally and spatially heterogeneous landscape. The data availability of new generation multispectral sensors of Landsat-8 (L8) and Sentinel-2 (S2) satellites offers unprecedented options for such applications. Given this, our study aims to display how the synergistic use of these optical sensors can efficiently support crop type mapping research while integrating an object-based image analysis (OBIA). Through the applied methods, we used the enhanced spatial and temporal adaptive reflectance fusion model (ESTARFM) and the flexible spatiotemporal data-fusion model (FSDAF) to blend L8 and S2 data and obtain reliable normalized difference vegetation index (NDVI) datasets with fine spatial and temporal resolution. Then the crop phenological information was extracted using a Savitzky–Golay filter and fused NDVI time series. Finally, a model combining phenological metrics and fused reconstructed NDVI as classification features was developed using a random forest (RF) classifier/OBIA approach. The results show that the FSDAF method creates more accurate fused NDVI and keeps more spatial details than ESTARFM. The FSDAF model was then used to create fused, high-resolution time-series products that were able to extract crop phenology in single-crop fields while providing a very detailed pattern relative to that from individual sensor time-series data. Moreover, combined L8 and S2 data by FSDAF produced highly significant overall classification accuracies (90.03% for pixel-based RF to 93.12% OBIA RF), outperforming individual sensor use (82.57% for L8-only; 88.45% for S2-only). Our proposed workflow highlights the advantage of spatiotemporal fusing and OBIA environment in spatiotemporally heterogeneous areas and fragmented landscapes, which represents a promising step toward generating fast, accurate, and ready-to-use agricultural data products.

Remote sensing offers spatially explicit and temporally continuous observational data of various land surface parameters such as vegetation index, land surface temperature, soil moisture, leaf area index, and evapotranspiration, which can be widely leveraged for various applications at different scales and contexts. One of the main applications is agricultural monitoring, where a smart system based on precision agriculture requires a set of satellite images with a high resolution, both in time and space to capture the phenological stages and fine spatial details, especially in landscapes with various spatial heterogeneity and temporal variation. These requirements sometimes cannot be provided by a single sensor due to the trade-off required between spatial and temporal resolutions and/or the influence of cloud cover. The data availability of new generation multispectral sensors of Landsat-8 (L8) and Sentinel-2 (S2) satellites offers unprecedented options for such applications. Given this, the current study aims to display how the synergistic use of these optical sensors can efficiently support such an application. Herein, this study proposes a deep learning spatiotemporal data fusion method to fill the need for predicting a dense time series of vegetation index with fine spatial resolution. The results show that the developed method creates more accurate fused NDVI time-series data that were able to derive phenological stages and characteristics in single-crop fields, while keeps more spatial details in such a heterogeneous landscape.

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.

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

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.

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 propose a new heuristic based approach to determine the optimal non-periodic inspection plan on a finite time horizon for a condition-based maintenance. The considered system consists of a single machine subject to a continuous, monotonous and stochastic degradation which can lead to failure and consequently to a maintenance action. The maintenance actions consist of replacing the main part of the production unit by another spare part. Spare parts are classified by their degradation into several qualities: New spare parts, which are provided by external supplier with a fixed delivery time. Used spare parts which are collected and provided by the maintenance service with fixed remanufacturing time, Depending on decision thresholds, the replacement might be either preventive or corrective. The objective is to determine the order/remanufacturing decision threshold (from which an order/remanufacturing is to be launched) and the preventive maintenance decision threshold to perform the preventive replacement. Our approach aims to minimize the total cost due to replacement, storage, inspection, order/remanufacturing costs and downtime penalty. A simulation-based genetic algorithm is proposed. At the end numerical examples are given to observe the performance of the proposed heuristic.

Input-output is a model which is highly employed in the field of information and communication technologies ICT. However, it can be used in many other scientific fields in order to give a perfect analysis. Throughout this model, we can determine the economic and social effects of the fishery products system in Morocco. Moreover, it can be considered as a basic model in order to study the integration level of fishery products system in the Morocco economy and the development effects of different segments of this system in the national economy of Morocco.

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