Efficient repairs of infeasible job shop problems by evolutionary algorithms

Efficient repairs of infeasible job shop problems by evolutionary algorithms Ra´ ul Menc´ ıaa,∗, Carlos Menc´ ıaa, Ramiro Varelaa aDepartment of Computer Science, University of Oviedo, Spain Abstract We address the task of repairing infeasibility in the context of infeasible job shop scheduling problems with a hard constraint on the maximum makespan allowed. For this purpose, we adopt a job-based view of repairs, that allows for dropping some of the jobs and so gives rise to the problem of computing the largest subset of jobs that can be scheduled under the makespan constraint. Recent work proposed a genetic algorithm for solving this problem, which integrates an efficient solution builder for defining the search space. In this paper, we build on this earlier work and make several contributions. We provide a formal analysis of both the search space and the solution builder. Then, we propose two important enhancements to the genetic algorithm: first, we develop a new solution builder aimed at reducing the number of feasibility tests, making the search process more efficient. In addition, we propose a more effective procedure for testing the feasibility of different subsets of jobs under the given makespan constraint based on the use of a light-weight genetic algorithm. Experimental results show that the proposed methods are effective at solving the problem, and that the enhancements bring significant improvements. Keywords: Job Shop Scheduling, Infeasibility, Repairs, Evolutionary Algorithms, Solution Builders 1. Introduction Scheduling problems arise profusely in a wide range of areas, especially in manufacturing and engineering, where a proper organization of limited resources is usually necessary. In addition, these problems are often computationally intractable, what makes them a natural application domain for advanced artificial intelligence and operations research methods. As a consequence, scheduling problems have been thoroughly studied in the literature over the last decades, giving rise to a large body of solving approaches, both exact and approximate, e.g. (Brucker et al., 1994; Nowicki and Smutnicki, 2005; Beck, 2007; Zhang et al., 2008; Menc´ ıa et al., 2015; Peng et al., 2015; Deng et al., 2020). ∗Corresponding author Email address: Preprint submitted to Engineering Applications of Artificial Intelligence June 26, 2021 Scheduling problems usually require computing schedules that optimize a given objective function. However, in some settings there can be constraints that make the problem infeasible, i.e., with no possible solution whatsoever. Such scenario may appear when, for instance, considering a hard constraint that imposes a limit on the maximum makespan allowed, enforcing all the jobs in the problem to be scheduled (and completed) by a given time limit. This kind of constraint is natural in practice, and infeasibility may easily arise under this constraint if the given scheduling horizon is too tight. Furthermore, a number of scheduling problems with a constraint on the makespan have been studied in the past, e.g. (Dawande et al., 2006; Allahverdi and Aydilek, 2014; Guyon et al., 2014; Choi, 2015)). In this context, beyond detecting infeasibility, users may be interested in identifying its causes, or in finding possible ways of repairing it, so that being able to solve the problem to some extent. In this paper, we address the task of repairing infeasible job shop scheduling problems with a hard constraint on the makespan. For this purpose, we adopt a job-based view of repairs, which enables dropping some of the jobs so that the remaining ones can be scheduled within the makespan constraint. This view was recently taken in (Menc´ ıa et al., 2019), giving rise to different notions of repairs, such as feasible subsets of jobs (FSJs), set-wise maximal feasible subsets of jobs (MFSJs) and feasible subsets of jobs of maximum cardinality (maxFSJs), i.e., feasible subsets of jobs with the greatest possible number of jobs. These concepts are inspired in analogous notions in the analysis of inconsistency in logic, where repairing (or correcting) inconsistent formulas has been widely investigated (Marques-Silva and Menc´ ıa, 2020). In addition, Menc´ ıa et al. (2019) preliminarily addressed the problem of approximating maxFSJs, by means of a genetic algorithm. This algorithm looks for solutions in the search space of (approximations of) MFSJs, defined by a solution builder used in its decoding phase. The genetic algorithm was recently adapted to a weighted version of the problem and combined with a local search algorithm specifically tailored to the case that jobs have different weights (Menc´ ıa et al., 2020). We focus on the problem of approximating maxFSJs, that is, computing the largest subsets of jobs that can be scheduled under the hard makespan constraint. Building on (Menc´ ıa et al., 2019), we make several contributions: •We first provide a formal analysis of the search space of MFSJs and the solution builder, proving relevant properties. •The analysis gives rise to important enhancements to the genetic algorithm. In this respect, we propose a new solution builder that defines the same search space but in a more efficient way. By integrating a binary search phase, it aims at reducing the number of feasibility tests needed to compute a solution, what allows for saving time. •Furthermore, we propose a new (incomplete) procedure for testing the feasibility of different subsets of the jobs (i.e. deciding whether these can be scheduled within the given makespan limit), which is iteratively invoked by the solution builders. Whereas earlier work used a greedy algorithm for this purpose, the new procedure integrates a light-weight genetic algorithm which is more effective, leading to better results. 2 We conducted an extensive experimental study to evaluate the proposed algorithms over a large set of instances with different sizes and characteristics. The experimental results reveal that genetic algorithms are successful at solving the problem and confirm that the new methods bring significant improvements in practice. The remainder of the paper is structured as follows: Section 2 introduces the necessary background and notation, including the definition of the problem. Section 3 reviews related work. Section 4 presents a formal analysis of the search space and the solution builder from (Menc´ ıa et al., 2019), and describes the new solution builder that exploits binary search. The main components of the genetic algorithm are presented in Section 5. The new procedure for testing the feasibility of a given subset of jobs is described in Section 6. Section 7 is devoted to the experimental study. Finally, we summarize the main conclusions and outline ideas for future research in Section 8. 2. Preliminaries In the classical job shop scheduling problem (JSP) we are given a set of njobs J={J1, . . . , Jn}that must be scheduled on a set of mresources or machines M={M1, . . . , Mm}. Job Ji∈ J consists of a sequence of mtasks or operations (θi1, . . . , θim), and each of its operations θij requires a particular machine M(θij)∈ M during a (positive integer) processing time pθij . Besides, without loss of generality, it is commonly assumed that any two operations of the same job require different machines. A schedule Sis an allocation of a starting time stθij to each operation satisfying the following constraints: i. Conjunctive constraints. Operations must be scheduled in the order they appear in their job, i.e., stθij +pθij ≤stθi(j+1) for all i= 1, ..., n and j= 1, ..., m −1. ii. Disjunctive constraints. Machines cannot process more than one operation at a time, that is, (stu+pu≤stv)∨(stv+pv≤stu)for all operations u, v with u6=vand M(u) = M(v). iii. Non-preemption. The processing of operations cannot be interrupted, i.e., Cu= stu+pufor every operation u, where Cudenotes the completion time of u. The quality of a schedule can be evaluated with respect to several different metrics (Brucker and Knust, 2006), such as the makespan,total flow time or tardiness and lateness measures (when due dates are considered), to name a few. In this work, we focus on the makespan: given schedule S, its makespan is defined as the maximum completion time of the operations in S, and it is denoted Cmax(S). This metric gives rise to one of most studied optimization versions of the JSP, denoted J||Cmax in the standard α|β|γnotation (Graham et al., 1979)), which requires computing a schedule with the minimum possible makespan. Taking the makespan into account, the decision version of the JSP requires determining whether there exists a schedule Ssuch that Cmax(S)≤C, where Cis a fixed limit on the maximum makespan allowed. If such a schedule Sexists, we call the problem instance feasible, whereas infeasible otherwise. The JSP, in its decision version, is well-known to be NP-complete (Garey et al., 1976). 3 This paper focuses on infeasible problem instances due to a hard constraint on the makespan and, more specifically, on the task of repairing infeasibility in the best possible manner. To this aim, we adopt a job-based view of repairs, that enables relaxing the problem by dropping some of the jobs in a way that the remaining ones can be scheduled within the makespan limit imposed by the hard constraint. Throughout, we will refer to such an infeasible instance by a pair I= (J, C), requiring scheduling the set of jobs Jwithout exceeding the maximum makespan C. In this setting, the following definitions serve to characterize different notions of repairs (Menc´ ıa et al., 2019): Definition 1. (FSJ) Given an infeasible instance I= (J, C),S(Jis a feasible subset of jobs (FSJ) of Jif and only if (S, C)is feasible. An FSJ is a subset of jobs that can be scheduled under the makespan constraint. Thus, it represents a possible way of repairing infeasibility. However, an arbitrary FSJ may leave out a number of jobs unnecessarily, and so considering some maximality criteria would be beneficial. Definition 2. (MFSJ) Given an infeasible instance I= (J, C),S(Jis a maximal feasible subset of jobs (MFSJ) of Jif and only if (S, C)is feasible and for all S0⊆ J with S(S0, (S0, C) is infeasible. Definition 3. (maxFSJ) Given an infeasible instance I= (J, C),S∗(Jis a maximum feasible subset of jobs (maxFSJ) if and only if (S∗, C)is feasible and for all FSJs S0of J,|S0| ≤ |S∗|. MFSJs and maxMFSJs exhibit different forms of maximality. On the one hand, MFSJs are maximal with respect to set inclusion, that is, no superset of an MFSJ is an FSJ. On the other hand, maxFSJs are maximal with respect to set cardinality, i.e., maxFSJs are the largest possible FSJs. As we will see in the following section, maxFSJs are MFSJs as well, but the opposite does not always hold true. Arguably, MFSJs represent a kind of local optima with respect to approximating maxFSJs, since these cannot be extended with any jobs without losing feasibility. These definitions build on related concepts in the analysis of inconsistent propositional formulas, such as maximal satisfiable subformulas (MSSes) or maximum satisfiability (maxSAT), representing analogous concepts to MFSJs and maxFSJs respectively (see (Marques-Silva and Menc´ ıa, 2020) for a recent survey). The following example (Menc´ ıa et al., 2019) illustrates all the definitions: Example 1. Let us consider a job shop with jobs J={J1, J2, J3, J4}and machines M={M1, M2}. Each job Jiconsists of a sequence of two operations (θi1, θi2), with processing times and machine requirements as indicated in Table 1 (e.g., job J1 consists of the sequence of operations (θ11, θ12);θ11 requires machine M1during 2 time units, and θ12 requires machine M2during 3 time units, ...). If we consider a hard constraint limiting the makespan to at most C= 10 the instance (J, C)is infeasible. There are 11 FSJs of J:∅,{J1},{J2},{J3},{J4}, {J1, J2},{J1, J3},{J1, J4},{J2, J3},{J2, J4}and {J1, J2, J4}as there exists a schedule with makespan less than or equal to 10 for each of them. Out of these 4 Table 1: Instance data. J1J2J3J4 θi12 (M1) 3 (M1) 6 (M2) 5 (M2) θi23 (M2) 2 (M2) 4 (M1) 5 (M1) J1θ11, M1θ12, M2 J2θ21, M1θ22, M2 J4θ41, M2θ42, M1 12345678910 Figure 1: Gantt chart of a schedule for the maxFSJ {J1, J2, J4}in Example 1. sets, three are MFSJs: {J1, J3},{J2, J3}and {J1, J2, J4}; and only the last one is a maxFSJ, with 3 jobs. Figure 1 shows a schedule for the maxFSJ with makespan 10, which does not exceed the limit C. With the definitions above, computing maxFSJs may be seen as the best way of repairing infeasibility, due to their maximum size. Hence, in this paper we address the maximization problem of approximating maxFSJs for a given infeasible instance (J, C), that is finding feasible subsets of jobs with maximum cardinality. Table 2 summarizes the main notation and terminology introduced in this section. It will be used throughout the paper. Table 2: Main notation and terminology. Notation Definition JSP Job shop scheduling problem MSet of machines Mii-th machine JSet of jobs Jii-th job θij j-th operation of job Ji stθij Starting time of operation θij pθij Processing time of operation θij CuCompletion time of operation u Cmax(S)Makespan of schedule S CMaximum makespan (J, C)Problem instance, with jobs Jand maximum makespan C FSJ Feasible subset of jobs MFSJ Maximal feasible subset of jobs maxFSJ Maximum feasible subset of jobs 5 3. Related work The problem studied in this paper was first addressed in (Menc´ ıa et al., 2019). In this previous work, the notions of MFSJ and maxFSJ were proposed as a means to repairing infeasibility in the context of job shop scheduling problems with a hard constraint on the makespan. These definitions are based on concepts commonly used in the field of Boolean satisfiability in the analysis of unsatisfiable propositional formulas. For approximating maxFSJs, Menc´ ıa et al. (2019) proposed a genetic algorithm that looks for solutions in the space of (approximations of) MFSJs. To this aim, it integrates a solution builder based on a linear search approach (Bailey and Stuckey, 2005; Marques-Silva et al., 2013) and uses a greedy algorithm (Giffler and Thompson, 1960) as an incomplete procedure to test the feasibility of subsets of jobs. To our knowledge, this genetic algorithm is the current best performing approach for solving the problem. This algorithm was later adapted to handle a weighted version of the problem and combined with a local search approach (Menc´ ıa et al., 2020). The local search approach is only applicable when jobs have different weights, so it cannot bring any benefits to the unweighted version of the problem considered herein. In contrast, improvements to the core components of the genetic algorithm can be expected to be effective in the weighted version of the problem as well. In this paper, we build on this earlier work and make significant contributions, in both theory and practice. First, we provide a detailed formal analysis proving relevant properties, as the completeness of the search space of MFSJs, and the soundness of the solution builder. In addition, we propose two key enhancements to the genetic algorithm: a new, more efficient, solution builder and a new procedure to test the feasibility of subsets of jobs more effectively. Despite restricting our study to the task of repairing infeasible job shop scheduling problems with a hard constraint on the makespan, the scope and applicability of this framework should be underscored. The same notions for repairing infeasible problem instances could be applied to other versions of job shop scheduling (e.g., considering setup times, uncertainty or additional constraints on the resources) or to other scheduling problems where the input is a set of jobs. Furthermore, the hard constraint that makes the problem instance infeasible could be defined on metrics other than the makespan. In any case, computing MFSJs and maxFSJs may be a suitable approach for dealing with infeasibility. In addition, the methodology in the formal analysis and the algorithms proposed herein could serve as a solid basis to tackle such problems in the future. In the remainder of this section, we first discuss some related problems and then review genetic algorithms for solving scheduling problems. 3.1. Related problems The problem of computing maxFSJs addressed in this paper is related to other problems studied in the field of scheduling. For example, Dawande et al. (2006) considered the problem of finding a feasible subset of jobs in a two-stage flow shop maximizing a weighted sum of the jobs. However, testing the feasibility of a two-stage flow shop can be done in polynomial time (Garey et al., 1976), whereas testing the feasibility of general job shop instances is an NP-complete problem. 6 Another related problem is the one addressed in (Della Croce et al., 2017), which considers polynomially solvable two machine flow shop and job shop problems, and focuses on selecting the set of jobs of a given fixed size (introduced as a parameter) that optimizes the makespan. In contrast, we focus on optimizing the size of the selected set of jobs, while fixing the limit on the maximum makespan allowed. The problem addressed herein can be also related to the classical objective function of minimizing the number of late, or tardy, jobs (Moore, 1968; Della Croce et al., 2000). In this setting, each job is associated a due date, and the goal is to compute a schedule that minimizes the number jobs that are completed after their indicated due dates. This objective function plays an important role in the context of overloaded single-machine real-time systems (Liao et al., 2019), where the goal is completing the maximum number of tasks on time. In this paper, our goal is not computing a schedule that optimizes a given objective function, but identifying the largest subset of jobs that can be scheduled under the given additional hard constraint, removing any other jobs that do not take part in the solution. 3.2. Genetic algorithms Genetic algorithms (GAs) stand out among the most successful population-based metaheuristics (Talbi, 2009). GAs were originally proposed by Holland (1975) and are inspired in the theory of evolution. These algorithms maintain a population of solutions which is evolved by the application of selection, recombination and replacement operators, with the goal of reaching an appropriate tradeoff between exploration of the search space and intensification in its most promising regions. Genetic algorithms have been widely used to solve a variety of hard scheduling problems, including single machine (Mustu and Eren, 2018; Menc´ ıa et al., 2019), parallel machines (Vallada and Ruiz, 2011; Tan et al., 2019), open shop (Andresen et al., 2008; Hosseinabadi et al., 2019), flow shop (Branda et al., 2021), job shop (Gonc¸alves and Resende, 2014; Zhang et al., 2020) or resource constrained project scheduling problems (Gonalves et al., 2008). In addition, GAs have been successfully applied in numerous domains, as heterogeneous computing systems Akbari et al. (2017) or operations management (Lee, 2018), to name a few. A large body of genetic algorithms has been proposed for solving job shop scheduling problems in their optimization versions. The performance of these algorithms relies on coding schemas specific to the problem, as well as on the use of sophisticated crossover operators. Some examples of coding schemas are those based on preference rules (Della Croce et al., 1995), permutations of jobs with repetitions (Bierwirth, 1995) or random keys (Gonc¸alves and Resende, 2014). Crossover operators play an important role in the evolutionary process, since these allow for an effective transmission of relevant characteristics from parents to their offspring. Examples of crossover operators include order-based crossover (Davis, 1985), multi-step crossover (Yamada and Nakano, 1995) or job-based order crossover (Ono et al., 1996), among others. In order to decode chromosomes into actual schedules, GAs commonly exploit schedule builders. These are methods that allow for restricting the search to subsets of all possible schedules. For instance, the well-known G&T algorithm (Giffler and Thompson, 1960) defines the space of the so-called active schedules. This algorithm has been extended to cope with variants of the job shop scheduling problem that include 7 additional elements and constraints, for instance sequence-dependent setup times (Artigues et al., 2005) uncertainty in the processing times (Palacios et al., 2014), or skilled operators that assist the processing of the operations (Menc´ ıa et al., 2015). Genetic algorithms have also been successfully combined with other metaheuristics, as local search methods. For example, Meeran and Morshed (2012) combined a genetic algorithm with tabu search to solve real-life job shop scheduling problems. Kurdi (2015) proposed a hybrid genetic algorithm which incorporates a self-adaptation strategy based on tabu search and random mutation operators. Hybrid genetic algorithms have also been successful in different variants of the problem, as dynamic (Kundakc and Kulak, 2016) or multiobjective (Gong et al., 2019) job shop scheduling problems, among others. 4. Search space The definition of a search space is a fundamental step towards solving hard combinatorial problems. Ideally, the search space would exhibit some desirable properties, such as being of reasonable size and containing high-quality solutions to the problem, including optimal ones. When facing scheduling problems, the use of so-called schedule builders is common for this purpose, e.g. (Giffler and Thompson, 1960; Kolisch, 1996; Artigues et al., 2005; Palacios et al., 2014; Menc´ ıa et al., 2015). Schedule builders, also referred to as schedule generation schemes, are constructive methods for computing and enumerating a subset of the schedules for a given problem instance, and so enable the definition of a search space. However, for solving the problem considered herein, i.e., approximating maxFSJs for a given infeasible problem instance, computing schedules alone does not suffice, since it is also necessary to identify feasible subsets of jobs. As a consequence, the definition of the search space needs to be done in two levels: first on the subset space of the set of all the jobs, and then on the set of schedules for any given subset of jobs in order to test its feasibility. We describe both in the following subsections. 4.1. Subset space of the set of jobs Our approach aims at restricting the search to the set of MFSJs, what comes with several benefits. First, the search space defined by the set of all MFSJs is complete, i.e., it contains all optimal solutions to any given problem instance. This follows from the fact that all maxFSJs are MFSJs as well, as proven next. Proposition 1. Let I= (J, C)be an infeasible problem instance and S∗(Ja maxFSJ of J.S∗is also an MFSJ of J. Proof. S∗is a maxFSJ of Jso, by Definition 3 it is an FSJ of J. Suppose that S∗is not an MFSJ of J. Then, by Definition 2, there must exist a proper superset S0(J of S∗which is also an FSJ of J. As S∗(S0, it necessarily follows that |S∗|<|S0|, so S∗is not a maxFSJ of J. A contradiction. FSJs exhibit a useful monotonicity property that will be used throughout. We prove that all the subsets of an FSJ are feasible subsets of jobs as well. 8 Proposition 2. Let I= (J, C)be an infeasible problem instance and S(Jan FSJ of J. Then, for all S0⊆ S,S0is an FSJ of J. Proof. Since Sis an FSJ of J, there exists a schedule Sfor the jobs in Swith Cmax(S)≤C. Given S0⊆ S, we can build a schedule S0by assigning each operation in S0the same starting time as in S.S0is a schedule for the jobs in S0and Cmax(S0)≤Cmax(S)≤C, as the operations in S0are a subset of those in S. Thus, by Definition 1, S0is an FSJ of J. A consequence of Proposition 2 is the dual result that all the supersets of an infeasible set of jobs are infeasible too, as proven next: Proposition 3. Let I= (J, C)be an infeasible problem instance and let U ⊆ J be such that the instance (U, C)is infeasible. Then, for all U0with U ⊆ U0⊆ J , the instance (U0, C)is infeasible. Proof. Consider an arbitrary U0such that U ⊆ U0⊆ J . Since, the instance (U, C) is infeasible and U ⊆ U0, not all the subsets of U0are FSJs. By the contrapositive of Proposition 2 it follows that that U0is not an FSJ of J, i.e., the instance (U0, C)is infeasible. It is clear that the number of MFSJs for any given problem instance is never greater than the number of FSJs since, by definition, all MFSJs are FSJs too. However, Proposition 2 allows for easily proving that the number of FSJs can be exponentially greater than that of MFSJs. Proposition 4. There are infeasible problem instances with a number of FSJs exponentially greater than the number of MFSJs. Proof. Consider a feasible problem instance (S, C)and a job j /∈ S such that the sum of the processing times of its operations exceeds C. The job jalone cannot be scheduled under the makespan constraint, i.e., the instance ({j}, C)is infeasible. Now define the instance (J, C), with J=S ∪ {j}. By Proposition 3, this instance is infeasible since {j}⊆J. The set Sis the only MFSJ of J, whereas by Proposition 2 each set in the power set of Sis an FSJ of J, that is, there are 2|S| FSJs of J. Noticeably, the monotonicity properties stated above enable an alternative definition of MFSJs: Proposition 5. Let I= (J, C)be an infeasible problem instance. S(Jis an MFSJ of Jif and only if (S, C)is feasible and for all j∈ J \ S,(S ∪ {j}, C)is infeasible. Proof. (If) The instance (S, C)is feasible, so Sis an FSJ of J. Let us suppose that Sis not an MFSJ of J. Then, there must exist an FSJ S0(Jsuch that S(S0. As S0is a proper superset of S,S0must contain some job j∈ J \ S. Since (S ∪ {j}, C) is infeasible for all j∈ J \ S, by Proposition 3, (S0, C)is necessarily infeasible. A contradiction. (Only if) Sis an MFSJ of Jso, by Definition 2, for all S0⊆ J such that S( S0, the instance (S0, C)is infeasible. Hence, for all j∈ J \ S,(S ∪ {j}, C)is infeasible. 9 feasibility of a given problem instance (J0, C), with J0⊆ J the G&T algorithm builds a schedule Sfor the jobs in J0scheduling, at each iteration, the operation in the set B(see Algorithm 3) that appears first in the operation sequence. We notice that the operation sequence contains all the operations of the jobs in J, so the operations of jobs not in J0are simply ignored. If the makespan of the computed schedule S does not exceed the maximum limit C, the instance is declared feasible (with Sbeing a witness that Jis a feasible set of jobs). Otherwise, although there is no guarantee that the instance is infeasible, the solution builder would handle it as such. This does not constitute a complete decision procedure, so the computed subset of jobs may not be an actual MFSJ, but an approximation instead. Anyway, the computed set is a feasible set of jobs, and its cardinality is the fitness value of the chromosome. Crossover and Mutation. The GA exploits the Job-based Order Crossover (JOX) (Ono et al., 1996) operator, which is particularly tailored to permutations with repetitions. It works as follows: given a pair of (parent) chromosomes, JOX selects a random subset of the job indices and copies them to the offspring in the same positions as they appear in the first parent. The remaining positions are filled from the second parent, maintaining their relative order. As an example, let us consider the following two chromosomes: Parent 1: (211323 1 23) Parent 2: (3 3 1 2 1 3 2 2 1) If the selected subset of jobs only includes the job 2, the generated offspring is: Offspring: (233121 3 21). The second offspring is obtained by the same procedure, but switching the role of the parents. On the other hand, the mutation operator introduces small changes by swapping two consecutive positions of the chromosome randomly. Overall integrated workflow. Figure 2 shows the overall workflow of the genetic algorithm. Given a problem instance and the GA parameters, the GA starts by generating and evaluating the initial population. Then, until the termination condition is met, the population evolves by undergoing selection, recombination, evaluation and replacement phases. At each generation, the chromosomes in the population are paired randomly (selection). In the recombination phase, each pair of chromosomes gives rise to two offspring, by the application of crossover and mutation operators. Then, the new individuals are evaluated, obtaining actual solutions from the chromosomes. To this aim, for each individual the job sequence and the operations sequence are extracted from the chromosome. Next, the solution builder is invoked, which is guided by the job sequence in the approximation of an MFSJ. For this purpose, either the one based on linear search (Algorithm 1) or the new one that integrates binary search (Algorithm 2) can be used. The solution builder makes several invocations to the procedure Feasible, which is guided by the operations sequence extracted from the chromosome. The implementation of this procedure is based on the G&T algorithm, as explained in this section. An improvement to this procedure is presented in the following section (Algorithm 5). After all the chromosomes are evaluated, the ones that will survive for the 16 Evaluation (J, C) Instance, GA parameters Generate and Evaluate Initial Population Selection Random Recombination Crossover and Mutation Extract job and operations sequences Solution Builder Alg. 1 or Alg. 2 Procedure Feasible G&T or Alg. 5 Replacement Tournament Terminate? FSJ with the greatest size found no yes Figure 2: Overall workflow of the genetic algorithm. next generation are those that are fitter, according to a tournament between parents and offspring (replacement). After the GA is run for the given number of generations, the FSJ with the greatest size found along the whole process is returned. 6. Improving the effectiveness of the decoding algorithms The decoding algorithms used by the GA aim at under-approximating an MFSJ efficiently by using the greedy G&T algorithm to test the feasibility of subsequent subsets of jobs. Arguably, using a greedy algorithm for this purpose represents the most efficient approach possible but, in turn, the approximations produced may not always be accurate. If only effectiveness is sought for, one could use a complete decision procedure; however, as already pointed out, using an exact algorithm, e.g. (Brucker et al., 1994; Beck, 2007; Menc´ ıa et al., 2014; Vil´ ım et al., 2015), may be too time consuming, making the approach impractical. Between these two extremes there is a 17 wide range of possibilities, such as using metaheuristics more effective (although more expensive) than greedy algorithms to test the feasibility of a given subset of jobs. Herein, we aim at improving the effectiveness of the decoding algorithms by means of an alternative implementation of the procedure Feasible used in Algorithms 1 and 2. To this aim, we propose an approach that not only issues the G&T algorithm for this task, but also uses a light-weight genetic algorithm, termed LWGA throughout, if the former fails at proving feasibility. The proposed method is shown in Algorithm 5. Given a set of jobs J0, a limit on the makespan Cand a probability PLW GA, the algorithm first computes a schedule S by using the greedy G&T algorithm. If the makespan of Sis not greater than C, the instance (J0, C)is efficiently declared feasible. Otherwise, the method performs a second phase with probability PLW GA (in this respect, the procedure Random(0,1) generates a random number in the interval [0,1] with uniform distribution). In this phase the procedure invokes LWGA, that searches for a schedule minimizing the makespan and returns the best schedule S0found after a short running time. Finally, if S0has a makespan not exceeding C, the instance is declared feasible, whereas otherwise the feasibility of the instance is deemed unknown. We note that the procedure returns a Boolean value indicating whether the instance (J0, C)has been proven feasible. In this regard, the value true means that a schedule with makespan not exceeding Chas been found and so the instance is feasible. In contrast, the value false does not mean that the instance is necessarily infeasible, but that a schedule with makespan not exceeding Chas not been found. So, Algorithm 5 is an incomplete (but sound) decision procedure. However, since it uses a more effective procedure for searching for high-quality schedules, it can be expected to detect feasibility more times than only using the G&T algorithm, thus leading to better approximations of MFSJs. In any case, whenever an instance is declared feasible, there is the guarantee that the result is correct, and so the computed approximations of MFSJs are correct as well. Moreover, although it is not shown in the pseudocode, the procedure exploits the operation sequences encoded in the chromosomes of the main GA both when issuing the G&T algorithm (as described in Section 5), and LWGA (as described below). So, it is integrated in the global search carried out by the main GA. Since the procedure Feasible is invoked many times along the execution of the main GA, in order to keep the overhead reasonably low, LWGA is only invoked with the given probability PLW GA introduced as a parameter. The value of this parameter is the same for all the invocations along the execution of the main GA. This way, the potential improvements are equally distributed among all the individuals. 6.1. Light-weight genetic algorithm (LWGA) As pointed out, LWGA searches for schedules aiming at minimizing the makespan. It follows the same general structure as the main GA, shown in Algorithm 4. However, since LWGA must not take a long running time, we need to limit its population size and number of generations to small values. In addition, LWGA terminates whenever it finds a schedule with a makespan less than or equal to the limit C. As the main GA described in Section 5, LWGA uses permutations with repetitions for encoding chromosomes. In this case, a chromosome only includes the tasks of the 18 Algorithm 5 Procedure Feasible. Data: Set of jobs J0, makespan limit C, probability PLW GA Result: Boolean value indicating that the instance (J0, C)has been proven feasible S←G&T(J0); if Cmax(S)≤Cthen return true; else if Random(0,1) ≤PLW GA then S0←LWGA(J0, C); if Cmax(S0)≤Cthen return true; end end return false jobs in J0, representing operation sequences. Besides, it uses the same crossover (JOX) and mutation operators. As decoding algorithm, LWGA exploits the G&T algorithm guided by the operation sequences encoded in the chromosomes. After building a schedule, the fitness of the individual is the makespan of the computed schedule. Furthermore, two additional processes are carried out as a means to effectively integrating LWGA in the global search process conducted by the main GA. First, in order to exploit the information encoded in a given chromosome cof the main GA for guiding the search in the space of schedules, LWGA creates its initial population by the following procedure: a chromosome c0is created by considering the tasks of the jobs in J0keeping their order as they appear in c, and the resulting chromosome c0is included in the population. Then another two chromosomes are generated by introducing small random perturbations to c0(by swapping two random positions of c0), which are included in the initial population as well. The remaining individuals are generated at random. This way, the characteristics of care included in the initial population of LWGA, but not in an extent that would cause it to converge very prematurely. On the other hand, when using LWGA, the main GA instruments a Lamarckian evolution model in order to transfer the characteristics that led to an improvement back to the main GA’s population. For this purpose, after an approximation of an MFSJ has been computed by the decoding algorithm of the main GA, if LWGA proved the feasibility of the subset of jobs, the corresponding chromosome cof the main GA is replaced by a chromosome c00 built as follows: the first positions of c00 correspond to the chromosome that led LWGA to compute a schedule for such subset of jobs J0without exceeding the makespan limit; then, the remaining positions of c00 are filled with the tasks of the remaining jobs in the order they appear in c. Lamarckian evolution models are commonly used by memetic algorithms, that combine a genetic algorithm with a local search procedure. However, these could also be expected of practical use in this this context. 19 7. Experimental results An experimental study was conducted to evaluate the methods proposed in this work. For this purpose, we coded a prototype in C++ implementing the algorithms and ran experiments on a Linux machine (Intel Xeon 2.26 GHz. 128 GB RAM). The experiments were carried out over a set of infeasible instances derived from classical JSP benchmarks from the OR-library (Beasley, 1990) as well as larger Taillard’s instances (Taillard, 1993). The benchmark set consists of instances of different sizes n×mwith a number of jobs n∈ {10,15,20,30,50}and a number of machines m∈ {5,10,15,20}. Specifically, we consider 5 instances of size 10 ×5: LA01-05; 5 instances of size 15 ×5: LA06-10; 6 instances of size 20 ×5: LA11-15 and FT20; 16 instances of size 10×10: LA016-20, ORB01-10 and FT10; 5 instances of size 15×10: LA21-25; 5 instances of size 20×10: LA26-30; 5 instances of size 30 ×10: LA31-35; 5 instances of size 15 ×15: LA36-40; 10 instances of size 50 ×15: tai50 15 01-10; and 10 instances of size 50 ×20: tai50 20 01-10. For each of these instances, three infeasible instances were built by fixing different values of the makespan limit Cto be 70%,80% and 90% of the optimal makespan of the JSP instance, denoted Copt. So, in all there are 216 instances. The goal of the experimental study is to assess the performance of the proposed methods. To this aim we compare three genetic algorithms, termed GALS, GABS and GA∗throughout. All these algorithms share the main structure and components described in Section 5, but differ in the solution builder used in the decoding phase. GALS uses the solution builder based on linear search depicted in Algorithm 1, whereas GABS exploits the two-phase solution builder that integrates a binary search phase shown in Algorithm 2. Both GALS and GABS use a single run of the greedy G&T algorithm (Algorithm 3) for testing the feasibility of different subsets of jobs. On the other hand, motivated by the first series of experiments shown below, GA∗integrates the two-phase solution builder, but using the procedure Feasible given in Algorithm 5, which issues the light-weight genetic algorithm (termed LWGA in Section 6) with a given probability PLW GA when the single run of the G&T algorithm fails at proving feasibility. We notice that GALS corresponds to the genetic algorithm proposed in (Menc´ ıa et al., 2019), which was shown to perform (much) better than a simple enumeration of random approximations of MFSJs. To our knowledge, this is the only algorithm proposed so far for the problem tackled in this paper, so it serves as a baseline method in the experimental evaluation. In all the experiments, the considered GAs evolve a population of 100 individuals with crossover probability of 0.9and mutation probability of 0.1until a termination condition is met (either completing a number of generations or surpassing a given time limit). In the case of GA∗, the underlying LWGA has the same crossover and mutation probabilities. The algorithms were run 20 times on each instance. Furthermore, in the experimental study the quality of the solutions computed is evaluated in terms of their error in percentage w.r.t. the best solution found for each instance along all the experiments. More concretely, if for a given instance the best known solution has Nbest jobs and an algorithm finds a solution with Njobs (with N≤Nbest), the error in percentage is computed as 100 ×(Nbest −N)/Nbest. Our first hypothesis is that GABS and GALS will yield similar results in terms of the 20 Table 3: Main notation used in the experimental study. Notation Definition nNumber of jobs mNumber of machines CMakespan limit Copt Optimal makespan LWGA Light-weight genetic algorithm PLW GA Probability of invoking LWGA in procedure Feasible (Algorithm 5) GALS GA with the solution builder based on linear search (Algorithm 1) GABS GA with the solution builder based on binary search (Algorithm 2) GA∗GA with the solution builder based on binary search issuing LWGA in procedure Feasible #cNumber of individuals (population size) for LWGA #gNumber of generations for LWGA GAPLW GA #c/#g GA∗using a probability PLW GA and setting the underlying LWGA with a population size of #cindividuals and #ggenerations quality of solutions reached, while GABS will be faster, since the solution builder with the binary search phase is expected to make less invocations to the procedure Feasible than the solution builder based on linear search. On the other hand, we expect GA∗to reach better solutions than GABS and GALS, due to a more effective implementation of the procedure Feasible, at the expense of longer running times. The experimental study is divided in three parts. We first compare GALS and GABS in order to assess the two solution builders. Then, we focus on GA∗and analyze the effect that the parameter PLW GA and the configuration of the underlying LWGA have on the overall performance of the algorithm. Finally, we provide a detailed comparison of the three genetic algorithms. Table 3 summarizes the main notation used in this section. 7.1. Comparing GALS and GABS We conducted a first series of experiments in order to compare the two solution builders and assess the efficiency gains that introducing a binary search phase has on the performance of the algorithm. For this purpose, we ran both GALS and GABS on the whole benchmark set, limiting the number of generations to 250. Table 4 summarizes the results. It shows the error (in percentage terms) of the best (Best) and average solutions (Avg.) obtained by each method over the 20 independent runs, as well as the computation times in seconds, averaged for each group of instances of the same size n×m. As we can observe, both algorithms yield solutions of similar quality regardless of the size of the instances, with only small variations that may be due to their stochastic nature. The two genetic algorithms are very effective at solving the smallest instances (up to size 20 ×5), obtaining solutions close to the best known ones, although the error grows for larger (and more challenging) instances, exceeding 10% on average for the largest ones of size 50 ×20. However, GABS is faster than GALS at completing the 250 generations. On average GABS takes less than 75% of the time taken by GALS. This indicates that the binary search phase included in the solution builder used by GABS is effective at saving feasibility tests, what enables reducing the overall computation time. Greater improvements 21 Table 4: Summary of results from GABS and GALS after evolving a population of 100 individuals over 250 generations. Best and average results (in terms of error in percentage) from 20 independent runs are reported. Running times are given in seconds. GALS GABS n×mBest Avg. T.(s) Best Avg. T.(s) 10 ×50.00 1.09 0.58 0.00 1.12 0.48 15 ×50.99 1.12 1.78 0.99 1.07 1.27 20 ×50.68 1.49 3.66 1.01 1.38 2.49 10 ×10 1.77 4.82 0.85 2.35 4.75 0.80 15 ×10 3.37 7.31 2.51 3.97 6.74 2.21 20 ×10 4.83 8.04 5.44 4.73 7.88 4.50 30 ×10 3.79 6.18 16.80 3.79 6.28 11.72 15 ×15 3.07 7.63 2.98 3.91 7.83 2.78 50 ×15 6.08 8.42 80.72 5.91 8.36 57.09 50 ×20 7.32 10.28 92.34 7.14 10.20 70.95 All 3.43 5.97 26.62 3.63 5.89 19.76 0 5 10 15 20 GALS 0 5 10 15 20 GABS (a) Up to 30 jobs 0 20 40 60 80 100 120 GALS 0 20 40 60 80 100 120 GABS (b) 50 jobs Figure 3: Scatter plots of the time taken (seconds) by GALS and GABS to complete 250 generations on the instances with (a) up to 30 jobs and (b) 50 jobs. are observed as the number of jobs grows, which does not come as a surprise since in these cases a larger number of tests can be saved by applying binary search. Figure 3 shows two scatter plots depicting the time taken by GALS and GABS to complete 250 generations for the instances with up to 30 jobs (Figure 3(a)) and for the largest instances with 50 jobs (Figure 3(b)). Each point represents the running time in seconds of GALS (horizontal axis) compared to GABS (vertical axis) on a given instance. Points below the diagonal indicate that GABS is faster than GABS. As can be observed, the difference in favor of GABS is greater with longer computation times. Noticeably, for the instances with 50 jobs, every point is far from the diagonal, which means that for these large instances, GABS is much faster than GALS. 22 Table 5: Summary of average results (error in percentage) from the configurations of GA∗after evolving a population of 100 individuals over 250 generations. PLW GA = 0.15 PLW GA = 0.5PLW GA = 1 #c/#g10/10 10/20 10/30 20/20 10/10 10/20 10/30 20/20 10/10 10/20 10/30 20/20 10 ×50.33 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 15 ×50.99 0.99 0.96 0.94 0.97 0.89 0.81 0.79 0.99 0.82 0.59 0.18 20 ×50.83 0.76 0.73 0.60 0.76 0.65 0.59 0.57 0.65 0.63 0.61 0.47 10 ×10 1.57 1.10 0.83 0.69 1.06 0.51 0.30 0.17 0.81 0.23 0.06 0.12 15 ×10 4.49 3.79 3.92 3.49 3.64 3.49 3.29 2.86 3.12 2.90 2.52 2.25 20 ×10 5.36 4.95 4.75 4.45 4.50 4.22 3.71 3.22 4.42 3.67 3.24 2.81 30 ×10 3.43 3.31 3.36 3.12 3.22 2.91 2.70 2.23 2.95 2.59 2.22 1.92 15 ×15 3.19 2.76 2.49 2.05 2.53 1.63 1.38 1.13 1.71 1.19 1.16 1.03 50 ×15 3.89 3.51 3.41 2.96 3.05 2.67 2.45 2.27 2.61 2.30 2.62 2.62 50 ×20 4.73 4.05 3.85 3.41 3.44 2.81 2.91 2.83 2.94 2.92 3.40 3.68 All 2.85 2.46 2.33 2.06 2.23 1.84 1.69 1.51 1.92 1.61 1.58 1.51 7.2. Analyzing GA∗ The second part of the experimental study is aimed at analyzing GA∗. As mentioned above, GA∗uses the procedure given in Algorithm 5 to test the feasibility of subsets of jobs. This procedure issues a light-weight genetic algorithm (LWGA) with a given probability PLW GA whenever the G&T algorithm fails at proving feasibility. So, it is expected to be (much) more time consuming than simply using the G&T algorithm for this purpose (as GALS and GABS do). As a consequence, and given the results in the previous subsection, GA∗uses the solution builder that integrates the binary search phase in order to save time. In these experiments we evaluate different values of the parameter PLW GA; concretely we consider values for PLW GA in {0.15,0.5,1}. In addition, we evaluate different configurations of LWGA in terms of population size and number of generations. In this respect, we consider four configurations: evolving a population of 10 individuals over 10, 20 and 30 generations, and a population of 20 individuals over 20 generations. Throughout we will use the notation GAPLW GA #c/#gto refer to GA∗using a given probability PLW GA and setting the underlying LWGA with a population size of #cindividuals and #ggenerations. Taking all into account, we consider 12 configurations of GA∗. We first evaluate the different versions of GA∗with the termination criterion of completing 250 generations. Besides, since some configurations may be too time consuming, we set a timeout of 3600 seconds in these experiments. Table 5 shows, for each configuration, the error on average of the solutions obtained over the 20 independent runs, averaged for groups of instances of the same size. On the other hand, Table 6 shows the time taken by each configuration in seconds. In both cases, the last row averages the results over all the instances. As we can observe in Table 5, the quality of the solutions improves with larger values of PLW GA in most cases. For most groups of instances, using PLW GA = 1 yields the best results. However, the largest instances of size 50 ×15 and 50 ×20 are the exception to this trend. In these cases, options with PLW GA = 0.5achieved the best results. This can be explained by the fact that for these large instances, some configurations with PLW GA = 1 were only able to complete a fraction of the 250 iterations 23 Table 6: Summary of the average time (in seconds) that each configuration of GA∗took to evolve a population of 100 individuals over 250 generations. PLW GA = 0.15 PLW GA = 0.5PLW GA = 1 #c/#g10/10 10/20 10/30 20/20 10/10 10/20 10/30 20/20 10/10 10/20 10/30 20/20 10 ×52.2 3.0 3.8 5.7 6.2 9.2 11.8 18.7 12.4 19.0 24.4 40.0 15 ×55.6 8.0 9.9 15.2 16.3 25.1 32.1 51.8 33.1 52.1 67.6 109.7 20 ×512.1 18.0 23.1 34.9 35.6 56.3 74.3 117.5 71.4 115.4 153.8 245.1 10 ×10 4.5 6.5 8.3 12.6 13.0 20.3 26.2 41.4 26.0 41.1 53.6 86.2 15 ×10 12.3 18.3 23.2 36.2 36.2 56.7 73.9 119.3 72.5 116.0 151.2 248.0 20 ×10 26.4 40.3 51.5 79.5 79.0 126.6 165.7 262.7 157.2 257.2 339.5 546.4 30 ×10 67.4 106.3 140.2 205.1 202.9 337.8 457.0 682.6 404.5 688.9 941.6 1411.4 15 ×15 16.8 25.5 33.1 50.5 50.2 80.0 105.8 167.4 100.1 162.5 219.1 349.3 50 ×15 397.1 658.4 912.4 1258.7 1206.6 2107.5 2988.6 3567.5 2388.6 3581.2 3600 3600 50 ×20 530.3 885.5 1229.5 1707.3 1619.9 2849.5 3600 3600 3212.4 3600 3600 3600 All 139.9 231.4 319.4 444.9 425.6 741.8 986.5 1106.5 843.8 1107.7 1149.8 1233.0 by the time limit of 3600 seconds. In the rest of the experiments, they completed them and produced the best results. Also, configurations with PLW GA = 0.5yielded better results than those with PLW GA = 0.15 for all the instance sets. On the other hand, assigning the LWGA larger values of population size and number of generations leads to better results as well. In most cases, the configurations that produce the least average error are those with GAPLW GA 20/20 , followed by GAPLW GA 10/30 , then GAPLW GA 10/20 and the configuration in the last position is normally GAPLW GA 10/10 . This ranking does not hold for PLW GA ∈ {0.5,1.0}on the largest instances, due to the reason mentioned above. These results indicate that the use of LWGA is effective at testing feasibility, and that issuing it more often and with larger population size and number of generations leads to better results in most cases. However, these improvements do not come without a cost. As shown in Table 6, running times grow significantly with PLW GA, as well as with the population size and number of generations of LWGA, being GA0.15 10/10 the most efficient approach, as could be expected. Note that for some configurations with PLW GA ∈ {0.5,1}running times are rather long, especially for the largest instances, where some of these configurations timed out before completing the 250 generations. Figure 4 shows two boxplots of the time taken (seconds) to complete 250 generations by the different configurations of GA∗on the instances with up to 30 jobs (Figure 4(a)) and 50 jobs (Figure 4(b)). We can see that, the larger the values of PLW GA, #cand #gare, the more time consuming the resulting algorithm is. Figure 5(a) shows a boxplot of the average errors for the 50 ×20 set, which illustrates the behaviour of the different configurations on the largest instances. As we can observe, the best configurations are those in the middle in terms of resource consumption, which reach a proper balance between the effort spent at each individual and the global search process that the genetic algorithm is able to conduct under the given conditions. In order to do a fair comparison, we conducted a series of experiments giving the algorithms the same time, letting the different configurations to perform as many generations as possible by the given time limit. Concretely, for an instance of size n×m, 24 GA0.15 10/10 GA0.15 10/20 GA0.15 10/30 GA0.15 20/20 GA0.5 10/10 GA0.5 10/20 GA0.5 10/30 GA0.5 20/20 GA1 10/10 GA1 10/20 GA1 10/30 GA1 20/20 0 200 400 600 800 1000 1200 1400 1600 1800 time (s) (a) Up to 30 jobs GA0.15 10/10 GA0.15 10/20 GA0.15 10/30 GA0.15 20/20 GA0.5 10/10 GA0.5 10/20 GA0.5 10/30 GA0.5 20/20 GA1 10/10 GA1 10/20 GA1 10/30 GA1 20/20 0 500 1000 1500 2000 2500 3000 3500 4000 time (s) (b) 50 jobs Figure 4: Boxplots of the time taken (seconds) by the different configurations of GA∗to complete 250 generations on the instances with (a) up to 30 jobs and (b) 50 jobs. GA0.15 10/10 GA0.15 10/20 GA0.15 10/30 GA0.15 20/20 GA0.5 10/10 GA0.5 10/20 GA0.5 10/30 GA0.5 20/20 GA1 10/10 GA1 10/20 GA1 10/30 GA1 20/20 0 1 2 3 4 5 6 7 8 9 error (%) (a) 250 generations GA0.15 10/10 GA0.15 10/20 GA0.15 10/30 GA0.15 20/20 GA0.5 10/10 GA0.5 10/20 GA0.5 10/30 GA0.5 20/20 GA1 10/10 GA1 10/20 GA1 10/30 GA1 20/20 0 2 4 6 8 10 12 error (%) (b) Timeout 1000 seconds Figure 5: Boxplots of the average error in percentage obtained for the instances of size 50 ×20, limiting the configurations of GA∗to (a) 250 generations and (b) 1000 seconds. we set the time limit to n×mseconds (which we believe is a reasonable choice). The results are summarized in Table 7, which reports the errors on average over the 20 independent runs produced by the different configurations, averaged for each group of instances, as well as the average values over the whole benchmark set. Looking at the results for the smallest instances, i.e., 10×5and 15×5, we can draw similar conclusions as to what we observed in the previous comparisons: the heavier configurations of GA∗ perform better, although with small differences in this case. However, as the size of the instances grows, this trend is inverted, favoring smaller values of PLW GA as well as smaller population size and number of generations of the underlying LWGA. Figure 5(b) shows a boxplot for the 50 ×20 instance set. We can see how the lighter versions of GA∗are now favored when comparing to the first series of experiments. Overall, the best configuration of GA∗seems to be GA0.15 10/20, since it yields the least average error if all the instances are considered. So, we will use this configuration 25 feasibility. Another interesting line for future research is the development of alternative algorithms, and their combination with the genetic algorithms proposed herein. In this respect, devising a local search approach, or even an exact method, seems promising. Finally, future efforts will target the task of repairing infeasibility considering other scheduling problems and hard constraints defined on metrics different from the makespan. Acknowledgements This research is supported by the Spanish Government under projects TIN201679190-R and PID2019-106263RB-I00, and by the Principality of Asturias under grant IDI/2018/000176. References Akbari, M., Rashidi, H., Alizadeh, S. H., 2017. An enhanced genetic algorithm with new operators for task scheduling in heterogeneous computing systems. Eng. Appl. Artif. Intell. 61, 35–46. Allahverdi, A., Aydilek, H., 2014. Total completion time with makespan constraint in no-wait flowshops with setup times. European Journal of Operational Research 238 (3), 724 – 734. Andresen, M., Brsel, H., Mrig, M., Tusch, J., Werner, F., Willenius, P., 2008. Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop. Mathematical and Computer Modelling 48 (7), 1279–1293. Artigues, C., Lopez, P., Ayache, P., 2005. Schedule generation schemes for the job shop problem with sequence-dependent setup times: Dominance properties and computational analysis. Annals of Operations Research 138, 21–52. Bailey, J., Stuckey, P. J., 2005. Discovery of minimal unsatisfiable subsets of constraints using hitting set dualization. In: PADL. pp. 174–186. Beasley, J. E., 1990. Or-library: Distributing test problems by electronic mail. J Oper Res Soc 41 (11), 1069–1072. Beck, J. C., 2007. Solution-guided multi-point constructive search for job shop scheduling. J. Artif. Intell. Res. 29, 49–77. Bierwirth, C., 1995. A generalized permutation approach to job shop scheduling with genetic algorithms. OR Spectrum 17, 87–92. Branda, A., Castellano, D., Guizzi, G., Popolo, V., 2021. Metaheuristics for the flow shop scheduling problem with maintenance activities integrated. Computers & Industrial Engineering 151, 106989. Brucker, P., Jurisch, B., Sievers, B., 1994. A branch and bound algorithm for the jobshop scheduling problem. Discret. Appl. Math. 49 (1-3), 107–127. 32 Brucker, P., Knust, S., 2006. Complex Scheduling. Springer. Choi, J. Y., 2015. Minimizing total weighted completion time under makespan constraint for two-agent scheduling with job-dependent aging effects. Computers & Industrial Engineering 83, 237 – 243. Davis, L., 1985. Applying adaptive algorithms to epistatic domains. In: Joshi, A. K. (Ed.), IJCAI. Morgan Kaufmann, pp. 162–164. Dawande, M., Gavirneni, S., Rachamadugu, R., 2006. Scheduling a two-stage flowshop under makespan constraint. Mathematical and Computer Modelling 44 (1), 73 – 84. Della Croce, F., Gupta, J. N., Tadei, R., 2000. Minimizing tardy jobs in a flowshop with common due date. European Journal of Operational Research 120 (2), 375 – 381. Della Croce, F., Koulamas, C., T’Kindt, V., 2017. A constraint generation approach for two-machine shop problems with jobs selection. Eur. J. Oper. Res. 259 (3), 898–905. Della Croce, F., Tadei, R., Volta, G., 1995. A genetic algorithm for the job shop problem. Comput. Oper. Res. 22 (1), 15–24. Deng, G., Su, Q., Zhang, Z., Liu, H., Zhang, S., Jiang, T., 2020. A population-based iterated greedy algorithm for no-wait job shop scheduling with total flow time criterion. Engineering Applications of Artificial Intelligence 88, 103369. Gallardo, J. E., Cotta, C., 2015. A grasp-based memetic algorithm with path relinking for the far from most string problem. Eng. Appl. Artif. Intell. 41, 183–194. Garc´ ıa, S., Fern´ andez, A., Luengo, J., Herrera, F., 2010. Advanced nonparametric tests for multiple comparisons in the design of experiments in computational intelligence and data mining: Experimental analysis of power. Inf. Sci. 180 (10), 2044–2064. Garey, M., Johnson, D., Sethi, R., 1976. The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research 1 (2), 117 – 129. Giffler, B., Thompson, G. L., 1960. Algorithms for solving production scheduling problems. Operations Research 8, 487–503. Gonalves, J., Mendes, J., Resende, M., 2008. A genetic algorithm for the resource constrained multi-project scheduling problem. European Journal of Operational Research 189 (3), 1171–1190. Gonc¸alves, J. F., Resende, M. G. C., 2014. An extended akers graphical method with a biased random-key genetic algorithm for job-shop scheduling. Int. Trans. Oper. Res. 21 (2), 215–246. Gong, G., Deng, Q., Chiong, R., Gong, X., Huang, H., 2019. An effective memetic algorithm for multi-objective job-shop scheduling. Knowledge-Based Systems 182, 104840. 33 Graham, R., Lawler, E., Lenstra, J., Kan, A., 1979. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics 5, 287 – 326. Guyon, O., Lemaire, P., Pinson, E., Rivreau, D., 2014. Solving an integrated job-shop problem with human resource constraints. Annals OR 213 (1), 147–171. Holland, J., 1975. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor. Hosseinabadi, A. A. R., Vahidi, J., Saemi, B., Sangaiah, A. K., Elhoseny, M., 2019. Extended genetic algorithm for solving open-shop scheduling problem. Soft Comput. 23 (13), 5099–5116. Kolisch, R., 1996. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation. European Journal of Operational Research 90 (2), 320 – 333. Kundakc, N., Kulak, O., 2016. Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem. Computers & Industrial Engineering 96, 31–51. Kurdi, M., 2015. A new hybrid island model genetic algorithm for job shop scheduling problem. Computers & Industrial Engineering 88, 273 – 283. Lee, C., 2018. A review of applications of genetic algorithms in operations management. Engineering Applications of Artificial Intelligence 76, 1 – 12. Liao, X., Zhang, H., Koshimura, M., Huang, R., Yu, W., 2019. Maximum satisfiability formulation for optimal scheduling in overloaded real-time systems. In: Nayak, A. C., Sharma, A. (Eds.), PRICAI. Vol. 11670 of Lecture Notes in Computer Science. Springer, pp. 618–631. Marques-Silva, J., Heras, F., Janota, M., Previti, A., Belov, A., 2013. On computing minimal correction subsets. In: IJCAI. pp. 615–622. Marques-Silva, J., Menc´ ıa, C., 2020. Reasoning about inconsistent formulas. In: IJCAI. pp. 4899–4906. Meeran, S., Morshed, M. S., 2012. A hybrid genetic tabu search algorithm for solving job shop scheduling problems: a case study. J. Intell. Manuf. 23 (4), 1063–1078. Menc´ ıa, C., Sierra, M. R., Menc´ ıa, R., Varela, R., 2019. Evolutionary one-machine scheduling in the context of electric vehicles charging. Integrated Computer-Aided Engineering 26, 49–63. Menc´ ıa, C., Sierra, M. R., Varela, R., 2014. Intensified iterative deepening a* with application to job shop scheduling. J. Intelligent Manufacturing 25 (6), 1245–1255. 34 Menc´ ıa, R., Menc´ ıa, C., Varela, R., 2019. Repairing infeasibility in scheduling via genetic algorithms. In: de Vicente, J. M. F., S´ anchez, J. R. ´ A., de la Paz L´ opez, F., Toledo-Moreo, F. J., Adeli, H. (Eds.), From Bioinspired Systems and Biomedical Applications to Machine Learning - 8th International Work-Conference on the Interplay Between Natural and Artificial Computation, IWINAC 2019, Almer´ ıa, Spain, June 3-7, 2019, Proceedings, Part II. Vol. 11487 of Lecture Notes in Computer Science. Springer, pp. 254–263. Menc´ ıa, R., Menc´ ıa, C., Varela, R., 2020. A memetic algorithm for restoring feasibility in scheduling with limited makespan. Natural Computing (Online First). Menc´ ıa, R., Sierra, M. R., Menc´ ıa, C., Varela, R., 2015. Memetic algorithms for the job shop scheduling problem with operators. Appl. Soft Comput. 34, 94–105. Menc´ ıa, R., Sierra, M. R., Menc´ ıa, C., Varela, R., 2015. Schedule generation schemes and genetic algorithm for the scheduling problem with skilled operators and arbitrary precedence relations. In: Proc. of ICAPS. AAAI Press, pp. 165–173. Moore, J. M., 1968. An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science 15 (1), 102–109. Mustu, S., Eren, T., 2018. The single machine scheduling problem with sequencedependent setup times and a learning effect on processing times. Applied Soft Computing 71, 291–306. Nowicki, E., Smutnicki, C., 2005. An advanced tabu search algorithm for the job shop problem. Journal of Scheduling 8, 145–159. Ono, I., Yamamura, M., Kobayashi, S., 1996. A genetic algorithm for job-shop scheduling problems using job-based order crossover. In: Proceedings of 1996 IEEE International Conference on Evolutionary Computation, Nayoya University, Japan, May 20-22, 1996. pp. 547–552. Palacios, J. J., Vela, C. R., Rodr´ ıguez, I. G., Puente, J., 2014. Schedule generation schemes for job shop problems with fuzziness. In: Proc. of ECAI. pp. 687–692. Peng, B., L, Z., Cheng, T., 2015. A tabu search/path relinking algorithm to solve the job shop scheduling problem. Computers & Operations Research 53, 154 – 164. Taillard, E., 1993. Benchmarks for basic scheduling problems. European Journal of Operational Research 64 (2), 278–285. Talbi, E., 2009. Metaheuristics - From Design to Implementation. Wiley. Tan, M., Yang, H. L., Su, Y. X., 2019. Genetic algorithms with greedy strategy for green batch scheduling on non-identical parallel machines. Memetic Comp. 11, 439–452. Vallada, E., Ruiz, R., 2011. A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. Eur. J. Oper. Res. 211 (3), 612–622. 35 Vil´ ım, P., Laborie, P., Shaw, P., 2015. Failure-directed search for constraint-based scheduling. In: CPAIOR. pp. 437–453. Yamada, T., Nakano, R., 1995. A genetic algorithm with multi-step crossover for jobshop scheduling problems. In: First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications. pp. 146–151. Zhang, C. Y., Li, P., Rao, Y., Guan, Z., 2008. A very fast TS/SA algorithm for the job shop scheduling problem. Computers and Operations Research 35, 282–294. Zhang, G., Hu, Y., Sun, J., Zhang, W., 2020. An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints. Swarm and Evolutionary Computation 54, 100664. 36