Abstract and 1. Introduction Abstract and 1. Introduction Abstract and 1. Introduction Mixed integer and constraint programming models
2.1 Mixed-integer linear programming model
2.2 Constraint Programming model


Constructive Heuristics


Benchmark instances


Numerical experiments
5.1 Experiments with the constructive heuristics
5.2 Solving the proposed models with a commercial solver


Conclusions and References Mixed integer and constraint programming models
2.1 Mixed-integer linear programming model
2.2 Constraint Programming model Mixed integer and constraint programming models Mixed integer and constraint programming models Mixed integer and constraint programming models 2.1 Mixed-integer linear programming model 2.1 Mixed-integer linear programming model 2.2 Constraint Programming model 2.2 Constraint Programming model Constructive Heuristics Constructive Heuristics Constructive Heuristics Constructive Heuristics Benchmark instances Benchmark instances Benchmark instances Benchmark instances Numerical experiments
5.1 Experiments with the constructive heuristics
5.2 Solving the proposed models with a commercial solver Numerical experiments Numerical experiments Numerical experiments 5.1 Experiments with the constructive heuristics 5.1 Experiments with the constructive heuristics 5.2 Solving the proposed models with a commercial solver 5.2 Solving the proposed models with a commercial solver Conclusions and References Conclusions and References Conclusions and References Conclusions and References 2 Mixed integer and constraint programming models In this section, we present mixed-integer linear programming (MILP) and constraint programming (CP) formulations for the FJS scheduling problem with sequencing flexibility and position-based learning effect. 2.1 Mixed-integer linear programming model The adoption of position-based decision variables serves as the fundamental approach for modeling problems involving position-based learning effects, as it enables a more natural expression of constraints related to the change in processing times. The proposed MILP model is derived from [4] and is built upon the model introduced in [25] that considers position-based decision variables; see also [26]. Notation below simplifies the presentation of the model. The MILP model follows. 2.2 Constraint Programming model Constraint Programming (CP) is a potent methodology widely employed for solving scheduling problems in academic and industrial literature. CP Optimizer [19], being an optimization commercial solver rooted in CP, incorporates specialized concepts of constraints and variables, significantly facilitating the modeling process for scheduling problems. In this section, we introduce a CP model specifically designed for its utilization in connection with CP Optimizer. The syntax of CP Optimizer is defined as it arises within the formulation. The model follows below. 3 Constructive Heuristics In this section, we propose two constructive heuristics for the FJS scheduling problem with sequencing flexibility and position-based learning effect. Constructive heuristics are algorithms that build a feasible solution from scratch by iteratively selecting and sequencing one operation at a time. The two proposed constructive heuristics are based on the earliest starting time (EST) rule [4] and the earliest completion time (ECT) rule [20]. The goal is to use them to provide an initial feasible solution to the exact solver that will be used to attempt to solve a set of test instances. Algorithm 4 presents the constructive heuristic based on the ECT rule. The algorithm is very similar to Algorithm 1, except for one detail. In the constructive heuristic based on EST, we first compute the instant rmin which is the earliest instant at which an unscheduled operation could be initiated. All operation/machine pairs that could start at that instant are considered and the pair with the shortest processing time is selected. But since they would all start at instant rmin, saying that the pair with the shortest processing time is chosen is the same as saying that the pair that ends earliest is selected. This is the idea that is taken to the extreme in the constructive heuristic based on the ECT rule: without limiting the choice to the operation/machine pairs that could start as early as possible, the operation/machine pair that will finish earliest is chosen, even if the processing of the operation does not start as early as possible. The worst case time complexity of Algorithm 4 is the same as that of Algorithm 1. The EST-based heuristic gives priority to those pairs operations/machines that can start the earliest. At the beginning of the construction, this corresponds, roughly, to giving priority to all the first operations of each job, which are operations that have no precedents (operations 1, 3 and 7 in the example of Figure 1). Still, due to the intention of scheduling operations as early as possible, it is possible that preference is given to empty machines, building solutions that use several machines. By rapidly scheduling the first operations of each job, more operations come to have their precedents scheduled, increasing the number of possibilities (search space) in future iterations of the method. On the other hand, the heuristic based on the ECT rule chooses the operation/machine pairs that terminate the earliest, regardless of whether they are the ones that can start the earliest or not. Such a strategy can limit the number of operation/machine pairs available in future iterations, reducing the search space of the method. Moreover, the choice for the operation/machine pair that can finish earliest, combined with the learning effect, leads the method to schedule operations on machines that already have several operations assigned to them, since the higher the position in the machine, the shortest de processing (reduced by the positioned-based learning effect). This leads to the construction of solutions in which not all machines are used. Depending on the learning rate α considered and the density of the DAG of precedences of the instance at hand, one heuristic may be better than the other. 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). Authors: 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). This paper is available on arxiv under CC by 4.0 Deed (Attribution 4.0 International) license. This paper is available on arxiv under CC by 4.0 Deed (Attribution 4.0 International) license. available on arxiv available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Algorithms That Learn as They Schedule: A Twin-Model Approach to Modern FJS

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

A Coarse-to-Fine Approach to Text-Guided 3D Localization Without Ground Truth

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

Pitting Heuristics Against Exact Solvers in the Flexible Job Shop Gauntlet

The Tortoise and the Hare: An Unexpected Scheduling Race Between MILP and CP Solvers

Impact of the Net Neutrality Repeal on Communication Networks: Abstract & Introduction

A Coarse-to-Fine Approach to Text-Guided 3D Localization Without Ground Truth

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

Pitting Heuristics Against Exact Solvers in the Flexible Job Shop Gauntlet

The Tortoise and the Hare: An Unexpected Scheduling Race Between MILP and CP Solvers

Impact of the Net Neutrality Repeal on Communication Networks: Abstract & Introduction

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps