Faster as You Go: Cracking Job-Shop Puzzles Where Tasks Learn on the Line

:::info Authors:

(1) K. A. G. Araujo, Department of Applied Mathematics, Institute of Mathematics and Statistics, University of Sao Paulo, Rua do Matao, 1010, Cidade Universitaria, 05508-090, Sao Paulo, SP, Brazil (kennedy94@ime.usp.br);

(2) E. G. Birgin, Department of Computer Science, Institute of Mathematics and Statistics, University of Sao Paulo, Rua do Matao, 1010, Cidade Universitaria, 05508-090, Sao Paulo, SP, Brazil (gbirgin@ime.usp.br);

(3) D. P. Ronconi, Department of Production Engineering, Polytechnic School, University of Sao Paulo, Av. Prof. Luciano Gualberto, 1380, Cidade Universitaria, 05508-010 Sao Paulo, SP, Brazil (dronconi@usp.br).

:::

Abstract and 1. Introduction

1. Mixed integer and constraint programming models

   2.1 Mixed-integer linear programming model

   2.2 Constraint Programming model

2. Constructive Heuristics

3. Benchmark instances

4. Numerical experiments

   5.1 Experiments with the constructive heuristics

   5.2 Solving the proposed models with a commercial solver

5. Conclusions and References

Abstract

This paper addresses the flexible job shop scheduling problem with sequencing flexibility and position-based learning effect. In this variant of the flexible job shop scheduling problem, precedence constraints of the operations constituting a job are given by an arbitrary directed acyclic graph, in opposition to the classical case in which a total order is imposed. Additionally, it is assumed that the processing time of an operation in a machine is subject to a learning process such that the larger the position of the operation in the machine, the faster the operation is processed. Mixed integer programming and constraint programming models are presented and compared in the present work. In addition, constructive heuristics are introduced to provide an initial solution to the models’ solvers. Sets of benchmark instances are also introduced. The problem considered corresponds to modern problems of great relevance in the printing industry. The models and instances presented are intended to support the development of new heuristic and metaheuristics methods for this problem.

\

1 Introduction

In this work, we consider the flexible job shop (FJS) scheduling problem with sequence flexibility and position-based learning effect. The problem is NP-hard, as it has the job shop scheduling problem, known to be NP-hard [13], as a particular case. The sequencing flexibility feature refers to the fact that the precedence constraints imposed on the operations of a job are given by an arbitrary directed acyclic graph instead of the usual linear order enforced in the FJS scheduling. Many real-life scheduling problems fit into this scope, such as, for example, problems in the printing industry [4, 21, 22], mold manufacturing industry [11], and glass industry [1]. In [22], the FJS with sequencing flexibility and several additional features, such as, for example, resumable operations, periods of unavailability of the machines, sequence-dependent setup times, partial overlapping between operations with precedence constraints, and fixed operations, was addressed. However, learning effects have not yet been taken into account in the literature regarding FJS with sequencing flexibility. The present work is devoted to this problem and presents the first step towards its effective and efficient resolution. Mixed integer linear programming (MILP) and constraint programming (CP) models and a relatively large set of instances are introduced for the purpose of producing a benchmark test set. Since, leaving aside very small instances, commercial exact solvers alone are hardly even able to find a feasible solution, constructive heuristics are proposed with the goal of enhancing their performance. Overall, this work takes a first step towards solving the proposed problem and provides a solid and robust basis for the future development of more sophisticated heuristic and metaheuristic methods.

\ In classical scheduling problems, the processing time of a given operation on a given machine is a fixed input parameter. However, there are real-life situations in which the manufacturing process involves repetitive manual tasks and the worker undergoes a learning process that results in a reduction of the execution time of his/her task. For instance, workers can get proficient at performing assemblies quickly, or more confident and skillful in manipulating hardware, software, and/or raw materials. If we consider that the reduction in the operation processing time is related to the number of times the worker has already performed the operation, we are dealing with a position-based learning effect. The pioneering works in applying the concept of learning effect to scheduling problems are [6, 9, 14]. Surveys on the subject can be found in [3, 7, 15].

\ A brief literature review in chronological order of the FJS with sequencing flexibility follows. In [12], the problem was addressed by considering non-fixed intervals of machine unavailability for preventive maintenance. A multi-objective MILP formulation and a hybrid multi-objective genetic algorithm were proposed. In [11] and [18], process flexibility was also taken into account, which means that the same result can be obtained with different operation sequences. In [11] a branch-and-bound algorithm was proposed, while [18] considered a symbiotic evolutionary algorithm. In [24], where a MILP formulation was presented to minimize the weighted tardiness, a hybrid bacterial foraging optimization algorithm was developed. Furthermore, the algorithm was enhanced by a local search method based on the manipulation of critical operations. A research that addresses the FJS with sequencing flexibility and sequence-dependent setup times can be found in [8]. The authors proposed a knowledge-based cuckoo search algorithm associated with a reinforcement learning strategy for self-adjustment. In [17], MILP and CP models and a hybrid evolutionary algorithm with local search mechanisms were introduced. A variation in which the processing of each operation requires multiple resources was considered in [16], in which models are presented and some properties of the problems are analyzed.

\ In [1], an application in the glass industry was described and a heuristic approach combining local search and priority rules was proposed to minimize the total cost related to final product completion times. Other industrial environments, such as the printing industry, have also been modeled as an FJS with sequencing flexibility. Regarding this particular application, [23] suggested a bi-objective genetic algorithm based on NSGA II to solve the problem. In [4], a MILP model and a constructive heuristic were presented, while [5] introduced a list scheduling algorithm and its extension to a beam search method. In [21, 22], formulations using constrained programming and mixed integer linear programming were established, as well as trajectory and population metaheuristics were introduced. In [27], it was considered the flight deck scheduling problem, which is an FJS with sequencing flexibility with additional constraints that state that some operations must be completed before others. The problem was described through its MILP formulation and instances were solved with a differential evolution type method. In [2], the scheduling of repair orders and worker assignment in an automotive repair shop was analyzed. The main scheduling problem is a two-resource FJS with sequencing flexibility. The problem was modeled by extending the formulation introduced in [4] and an iterated greedy heuristic was presented.

\ Let us consider an illustrative example of the FJS with sequencing flexibility and positionbased learning effect. The example has 12 operations and 3 machines. Figure 1 shows the precedence relationships between the operations and the standard processing times of each operation on each machine. The small table with the standard processing times shows that in the FJS scheduling problem each operation can be processed by one or more machines (situation known as routing flexibility), in opposition to the job shop (JS) scheduling problem in which each operation can be processed by only one machine. The concept of job is implicitly defined by the directed acyclic graph (DAG) and corresponds to a set of operations that have some dependency relationship between them. The figure makes it clear that, in the FJS scheduling problem with sequence flexibility, the dependencies of the operations of a job are given by an arbitrary acyclic directed graph as opposed to the total order of the FJS scheduling problem. In this example there are two jobs, one with 6 operations (numbered from 1 to 6) and the other also with 6 operations (numbered from 7 to 12).

\ A feasible solution to the instance of Figure 1 can be illustrated by a DAG in which a source node s and a target node t are added to the DAG that represents the precedence constraints; see Figure 2. Arcs from s to all operations with no predecessors and from all nodes without successor to t must also be added. (For the readers that can see the figure in colors, those arcs are painted purple.) In addition, dashed arcs represent the sequence (list) in which operations are processed by each machine. (For the readers that can see the figure in colors, blue corresponds to machine 1, violet corresponds to machine 2, and orange corresponds to machine 3.) Colored figures at the top or bottom of the operations correspond to their processing times. In this directed graph, that we name G = (V, A) from now on[1], the longest path from s to t corresponds to the makespan. In this example, the longest path, with value 80, corresponds to the path s, 1, 2, 4, 5, 6, t. (Highlighted yellow in the figure for those readers who can see the figure in color.) The depicted feasible solution corresponds to an optimal solution. Figure 3 shows the Gantt chart representation of the solution. Note that standard times were used, i.e. in this example the learning effect was not considered at all.

\

\

\ The rest of this paper is organized as follows. In Section 2, we introduce the integer linear programming and constraint programming models. In Section 3, we outline the proposed constructive heuristics. In Section 4, we report the introduced instances. Numerical experiments with the constructive heuristics and exact commercial solvers are reported in Section 5. Conclusions and lines of future research are presented in the concluding section.

\

:::info This paper is available on arxiv under CC by 4.0 Deed (Attribution 4.0 International) license.

:::