problem solving mathematical investigation and modelling topics

• WordPress.org
• Documentation
• Learn WordPress
• Members Newsfeed

Mathematics Investigations Teaching Resources

• Math Education

Mathematics is not just a subject of cold calculations and abstract symbols. It is a vibrant field of inquiry where learners can explore, discover, and understand the patterns that govern the world around us. One of the most effective ways to ignite students’ interest and deepen their understanding is through mathematical investigations. The incorporation of rich teaching resources in these explorations can significantly enhance the learning experience.

What are Mathematics Investigations?

Mathematics investigations are open-ended tasks that allow students to apply mathematical concepts and skills creatively to solve problems. Unlike traditional exercises with predetermined outcomes, investigations encourage learners to pose questions, formulate hypotheses, experiment with strategies, and draw conclusions based on their findings. They foster critical thinking, problem-solving, and communication skills as students work individually or collaboratively to navigate through their mathematical journey.

The Role of Teaching Resources in Mathematics Investigations

To facilitate successful mathematics investigations, teachers need to equip their classrooms with a variety of resources that cater to diverse learning styles and assist in delving deeper into concepts. Here are several key resources and how they can be integrated into teaching:

1.Manipulatives and Models

Physical objects like base-ten blocks, fraction circles, algebra tiles, and geometric shapes can help students visualize and manipulate mathematical ideas. When learners handle these manipulatives, they build concrete understanding before moving on to more abstract notions.

2.Digital Tools and Software

Technology offers dynamic possibilities for mathematical investigations. Interactive software such as Geometer’s Sketchpad or graphing calculators enable students to experiment with geometric shapes, analyze data, and explore algebraic expressions with immediate feedback.

3.Storybooks and Literature

Integrating literature into math lessons can provide context for investigations that resonate with students’ experiences. Picture books or stories involving math problems spark creativity and help learners see the relevance of mathematics in everyday life.

4.Games and Puzzles

Games engage students in a fun yet challenging way by incorporating mathematical thinking into play. Puzzles like Sudoku or logic problems promote strategic reasoning as students work towards solutions.

5.Project-Based Learning Kits

Curated project kits can offer comprehensive materials for conducting in-depth investigations on certain topics such as number theory or probability. They usually come with instructions, scenarios for inquiry, and all necessary components for execution.

6.Real-World Data Sets

Using data from real-world contexts makes mathematics meaningful. Whether it’s sports statistics, weather patterns or financial charts – when students analyze actual data sets, they develop analytical skills that are applicable outside the classroom.

Combining mathematics investigations with a wealth of teaching resources not only enriches learning but also prepares students for a future where they can apply their skills effectively in various contexts. It’s about creating an environment where curiosity drives exploration, mistakes are seen as learning opportunities, and persistence in problem-solving is cultivated. With the right blend of resources at their disposal, educators can guide their students towards becoming not just competent mathematicians but also lifelong learners who value the beauty and utility of mathematics.

Related Articles

Connecting mathematics to fun and practical applications can make it a favorite…

Mathematics forms an integral part of educational curriculums around the world, establishing…

Composite numbers are integers that have more than two distinct positive divisors.…

Pedagogue is a social media network where educators can learn and grow. It's a safe space where they can share advice, strategies, tools, hacks, resources, etc., and work together to improve their teaching skills and the academic performance of the students in their charge.

If you want to collaborate with educators from around the globe, facilitate remote learning, etc., sign up for a free account today and start making connections.

Pedagogue is Free Now, and Free Forever!

• New? Start Here
• Frequently Asked Questions
• Privacy Policy
• Terms of Service
• Registration

Don't you have an account? Register Now! it's really simple and you can start enjoying all the benefits!

We just sent you an Email. Please Open it up to activate your account.

I allow this website to collect and store submitted data.

Mathematics investigation

At its core, mathematics is about problem-solving and modelling the world around us. By giving students meaningful problems to solve they are engaged and can apply their learning, thereby deepening their understanding. Using a guided investigation model ensures that students stay focused on the mathematics being used and make connections to other areas of learning.

After students have been taught a skill or concept it is important that they apply it in a meaningful context as this will reveal the depth of their understanding. A guided inquiry is one way to do this. By scaffolding the problem, the teacher can lead students through a problem-solving exercise, highlighting the mathematics they need to use. Starting with a prompt – either a picture or a question – students can explore different ways of approaching the problem and communicating their thinking. Mathematics investigation links directly to the Critical and Creative Capability in the Australian Curriculum (Version 9.0) .

Investigations can be differentiated by adjusting the complexity of the original problem or the expected outcomes. Investigations can be assessed and guided through the use of rubrics. A rubric for assessment is usually in the form of a matrix or grid. It is used to interpret and assess a student's work against identified criteria. A student can use the rubric to self-assess their own work. 

By using a particular scaffold or approach regularly, students learn what is expected of them and are able to improve and develop their problem-solving skills. Teachers should explicitly teach how to approach a problem using such a scaffold. Popular scaffolds or protocols for guided investigations include:

Inquiry Maths

• Three-Act Tasks

To teach a Three-Act Task on the topic of ‘proportion and ratio’ include the following components, noting a Three-Act Task is a task consisting of three distinct sections.

• An engaging and perplexing Act One, often a video. Students discuss what they saw, pose questions and decide what information is needed for them to be able to answer the questions they have posed.
• An information and solution-seeking Act Two. Students are given the information they need and work, either in small groups or individually, to find a solution.
• A solution-discussion and revealing Act Three. Students discuss their findings and the solution is revealed. Students may then discuss and pose further questions.

The teacher:

• explicitly teaches the mathematics needed for the task
• explicitly teaches how to use a scaffold or protocol
• makes the learning intention and success criteria clear
• invites questions and wonderings
• focuses the students on the mathematical ideas being developed
• makes connections to students’ previous learning
• makes connections to other subject areas
• encourages students to work collaboratively
• monitors students, giving specific feedback to guide the students further.

The students:

• know how to use a particular scaffold or approach when working on a maths investigation to solve a problem
• know how to work collaboratively and respectfully
• communicate their ideas and thinking clearly
• ask questions and respectfully respond to other’s questions
• are prepared to struggle and make mistakes in order to make progress in their learning.

Examples of the strategy in action

Thinking mathematically

In this video, a teacher discusses how they used an investigation to reinforce the students’ understanding of estimation and prediction.

Nana's chocolate milk

A Three-Act Task on proportion and ratio. 

The Inquiry Maths website showcases a model of guided inquiry that encourages students to apply their knowledge based on a given prompt.

Open Middle problems

In an Open Middle problem an expression is presented and students are challenged to find the numbers that will make the expression true. They are challenging, suitable for all year levels, cover most maths topics, and promote problem-solving and reasoning skills. On this site you will find a comprehensive range of problems.

Transforming tasks strategy: from procedure to problem solving

Tasks are presented as following a ‘before and after’ approach. It demonstrates how to move from a procedural approach to posing questions that incorporate more of a problem-solving approach and mathematical investigation.

• All courses
• For Teachers
• For Students

Problem Solving, Mathematical Investigation, and Modeling (6081)

This course intends to enhance the students’ knowledge and skills in dealing with real-life and/or non-routine applications of mathematics. Students will have the opportunity to explore the use of problem-solving strategies or heuristics as they engage in mathematical investigations, formulate and justify conjectures, make generalizations, and communicate mathematical ideas.

• Teacher: MELANIE GURAT
• Enrolled students: 2

Mathematics for Teaching

This site is NOT about making mathematics easy because it isn't. It is about making it make sense because it does.

Exercises, Problems, and Math Investigations

The quality of mathematics students learn depends on the mathematical tasks or activities we let our students engage in.

Mathematical activities/tasks can be categorized into three types: exercises, problem solving, and math investigations.

Standard exercises

These are activities with clearly defined procedure/strategy and goal. Standard exercises are used for mastery of a newly learned skill – computational, use of an instrument, and even new terms or vocabulary. These are important learning activities but must be used in moderation. If our teaching is dominated by these activities, students will begin to think mathematics is about learning facts and procedures only. This is very dangerous.

Problem solving activity

These are activities involving clearly defined goals but the solutions or strategies are not readily apparent. The student makes decision on the latter. If the students already know how to solve the problem then it is no longer a problem. It is an exercise. Click  here  for features of good problem solving tasks. It is said that problem solving is at the heart of mathematics. Can you imagine mathematics without problem solving?

Math investigations

These are activities that involve exploration of open-ended mathematical situation. The student is free to choose what aspects of the situation he or she would like to do and how to do it. The students pose their own problem to solve and extend it to a directions they want to pursue. In this activity, students experience how mathematicians work and how to conduct a mathematical research. I know there are some parents and teachers who don’t like math investigation. Here are some few reason why we need to let our students to go through it.

• Students develop questions, approaches, and results, that are, at least for them, original products
• Students use the same general methods used by research mathematicians. They work through cycles of data-gathering, visualization, abstraction, conjecturing and proof.
• It gives students the opportunity communicate mathematically: describing their thinking, writing definitions and conjectures, using symbols, justifying their conclusions, and writing and reading mathematics.
• When the research involves a class or group, it becomes a ‘community of mathematicians’ sharing and building on each other’s questions, conjectures and theorems.

Students need to be exposed to all these type of mathematical activities. It is unfortunate that  textbooks and  many mathematics classes are dominated by exercises rather than problem solving and investigations tasks, creating the misconception that mathematics is about mastering skills and following procedures and not a way of thinking and communicating.

Samples of these tasks are shown in the picture below:

• Click to share on Facebook (Opens in new window)
• Click to share on LinkedIn (Opens in new window)
• Click to share on Twitter (Opens in new window)
• Click to share on Reddit (Opens in new window)
• Click to email a link to a friend (Opens in new window)

View All Posts

8 thoughts on “ Exercises, Problems, and Math Investigations ”

I would add a fifth important advantage of investigations. Students become more accustomed to not knowing what is coming next. This is educationally significant, although an uncomfortable situation to be in.

I suggest that on math investigation please put some problems and a solution.:)

An intriguing discussion is definitely worth comment.

I think that you need to write more on this subject matter, it may not be a taboo subject but typically people don’t talk about such topics. To the next! Best wishes!!

• Pingback: Top 20 Math Posts and Pages in 2012 - Mathematics for Teaching
• Pingback: » Theories and ideas behind the math lessons in this blog » Mathematics for Teaching

if juan cut a144-inch-long piece of wood into 8-inch pieces, how many pieces will he have. this is a promble-sloving investigation: math. choose a strategy

• Pingback: » What is mathematical investigation? » Mathematics for Teaching
• Pingback: Mathematics and Multimedia Blog Carnival #2 « Mathematics and Multimedia

Comments are closed.

• Our Mission

Using Mathematical Modeling to Get Real With Students

Unlike canned word problems, mathematical modeling plunges students into the messy complexities of real-world problem solving.  

How do you bring math to life for kids? Illustrating the boundless possibilities of mathematics can be difficult if students are only asked to examine hypothetical situations like divvying up a dessert equally or determining how many apples are left after sharing with friends, writes third- and fourth- grade teacher Matthew Kandel for Mathematics Teacher: Learning and Teaching PK-12 .

In the early years of instruction, it’s not uncommon for students to think they’re learning math for the sole purpose of being able to solve word problems or help fictional characters troubleshoot issues in their imaginary lives, Kandel says. “A word problem is a one-dimensional world,” he writes. “Everything is distilled down to the quantities of interest. To solve a word problem, students can pick out the numbers and decide on an operation.” 

But through the use of mathematical modeling, students are plucked out of the hypothetical realm and plunged into the complexities of reality—presented with opportunities to help solve real-world problems with many variables by generating questions, making assumptions, learning and applying new skills, and ultimately arriving at an answer.

In Kandel’s classroom, this work begins with breaking students into small groups, providing them with an unsharpened pencil and a simple, guiding question: “How many times can a pencil be sharpened before it is too small to use?”

Setting the Stage for Inquiry 

The process of tackling the pencil question is not unlike the scientific method. After defining a question to investigate, students begin to wonder and hypothesize—what information do we need to know?—in order to identify a course of action. This step is unique to mathematical modeling: Whereas a word problem is formulaic, leading students down a pre-existing path toward a solution, a modeling task is “free-range,” empowering students to use their individual perspectives to guide them as they progress through their investigation, Kandel says. 

Modeling problems also have a number of variables, and students themselves have the agency to determine what to ignore and what to focus their attention on. 

After inter-group discussions, students in Kandel’s classroom came to the conclusion that they’d need answers to a host of other questions to proceed with answering their initial inquiry: 

• How much does the pencil sharpener remove? 
• What is the length of a brand new, unsharpened pencil? 
• Does the pencil sharpener remove the same amount of pencil each time it is used?

Introducing New Skills in Context

Once students have determined the first mathematical question they’d like to tackle (does the pencil sharpener remove the same amount of pencil each time it is used?), they are met with a roadblock. How were they to measure the pencil if the length did not fall conveniently on an inch or half inch? Kandel took the opportunity to introduce a new target skill which the class could begin using immediately: measuring to the nearest quarter inch. 

“One group of students was not satisfied with the precision of measuring to the nearest quarter inch and asked to learn how to measure to the nearest eighth of an inch,” Kandel explains. “The attention and motivation exhibited by students is unrivaled by the traditional class in which the skill comes first, the problem second.” 

Students reached a consensus and settled on taking six measurements total: the initial length of the new, unsharpened pencil as well as the lengths of the pencil after each of five sharpenings. To ensure all students can practice their newly acquired skill, Kandel tells the class that “all group members must share responsibility, taking turns measuring and checking the measurements of others.” 

Next, each group created a simple chart to record their measurements, then plotted their data as a line graph—though exploring other data visualization techniques or engaging students in alternative followup activities would work as well.

“We paused for a quick lesson on the number line and the introduction of a new term—mixed numbers,” Kandel explains. “Armed with this new information, students had no trouble marking their y-axis in half- or quarter-inch increments.” 

Sparking Mathematical Discussions

Mathematical modeling presents a multitude of opportunities for class-wide or small-group discussions, some which evolve into debates in which students state their hypotheses, then subsequently continue working to confirm or refute them. 

Kandel’s students, for example, had a wide range of opinions when it came to answering the question of how small of a pencil would be deemed unusable. Eventually, the class agreed that once a pencil reached 1 ¼ inch, it could no longer be sharpened—though some students said they would be able to still write with it. 

“This discussion helped us better understand what it means to make an assumption and how our assumptions affected our mathematical outcomes,” Kandel writes. Students then indicated the minimum size with a horizontal line across their respective graphs. 

Many students independently recognized the final step of extending their line while looking at their graphs. With each of the six points representing their measurements, the points descended downward toward the newly added horizontal “line of inoperability.” 

With mathematical modeling, Kandel says, there are no right answers, only models that are “more or less closely aligned with real-world observations.” Each group of students may come to a different conclusion, which can lead to a larger class discussion about accuracy. To prove their group had the most accurate conclusion, students needed to compare and contrast their methods as well as defend their final result. 

Developing Your Own Mathematical Models

The pencil problem is a great starting point for introducing mathematical modeling and free-range problem solving to your students, but you can customize based on what you have available and the particular needs of each group of students.

Depending on the type of pencil sharpener you have, for example, students can determine what constitutes a “fair test” and set the terms of their own inquiry. 

Additionally, Kandel suggests putting scaffolds in place to allow students who are struggling with certain elements to participate: Simplified rulers can be provided for students who need accommodations; charts can be provided for students who struggle with data collection; graphs with prelabeled x- and y-axes can be prepared in advance.

.css-1sk4066:hover{background:#d1ecfa;} 7 Real-World Math Strategies

Students can also explore completely different free-range problem solving and real world applications for math . At North Agincourt Jr. Public School in Scarborough, Canada, kids in grades 1-6 learn to conduct water audits. By adding, subtracting, finding averages, and measuring liquids—like the flow rate of all the water foundations, toilets, and urinals—students measure the amount of water used in their school or home in a single day. 

Or you can ask older students to bring in common household items—anything from a measuring cup to a recipe card—and identify three ways the item relates to math. At Woodrow Petty Elementary School in Taft, Texas, fifth-grade students display their chosen objects on the class’s “real-world math wall.” Even acting out restaurant scenarios can provide students with an opportunity to reinforce critical mathematical skills like addition and subtraction, while bolstering an understanding of decimals and percentages. At Suzhou Singapore International School in China, third- to fifth- graders role play with menus, ordering fictional meals and learning how to split the check when the bill arrives. 

Let's Connect

Contact details.

Brgy. Atabay, Hilongos, Leyte, Philippines 6524

+639 17-306-5169

Get in Touch

Your Phone Number

Your E-mail

• Glenn’s Memoir
• Online Admission

Want to receive push notifications for all major on-site activities?

This Area is Widget-Ready

You can place here any widget you want!

You can also display any layout saved in Divi Library.

Let’s try with contact form:

share this!

August 30, 2024

This article has been reviewed according to Science X's editorial process and policies . Editors have highlighted the following attributes while ensuring the content's credibility:

fact-checked

trusted source

Different mathematical solving methods can affect how information is memorized

by University of Geneva

The way we memorize information—a mathematical problem statement, for example—reveals the way we process it. A team from the University of Geneva (UNIGE), in collaboration with CY Cergy Paris University (CYU) and Bourgogne University (uB), has shown how different solving methods can alter the way information is memorized and even create false memories.

By identifying learners' unconscious deductions, this study opens up new perspectives for mathematics teaching. These results are published in the Journal of Experimental Psychology: Learning, Memory, and Cognition .

Remembering information goes through several stages: perception, encoding—the way it is processed to become an easily accessible memory trace—and retrieval (or reactivation). At each stage, errors can occur, sometimes leading to the formation of false memories .

Scientists from the UNIGE, CYU and Bourgogne University set out to determine whether solving arithmetic problems could generate such memories and whether they could be influenced by the nature of the problems.

Unconscious deductions create false memories

When solving a mathematical problem , it is possible to call upon either the ordinal property of numbers, i.e., the fact that they are ordered, or their cardinal property, i.e., the fact that they designate specific quantities. This can lead to different solving strategies and, when memorized, to different encoding.

In concrete terms, the representation of a problem involving the calculation of durations or differences in heights (ordinal problem) can sometimes allow unconscious deductions to be made, leading to a more direct solution. This is in contrast to the representation of a problem involving the calculation of weights or prices (cardinal problem), which can lead to additional steps in the reasoning, such as the intermediate calculation of subsets.

The scientists therefore hypothesized that, as a result of spontaneous deductions, participants would unconsciously modify their memories of ordinal problem statements, but not those of cardinal problems.

To test this, a total of 67 adults were asked to solve arithmetic problems of both types, and then to recall the wording in order to test their memories. The scientists found that in the majority of cases (83%), the statements were correctly recalled for cardinal problems.

In contrast, the results were different when the participants had to remember the wording of ordinal problems, such as: "Sophie's journey takes 8 hours. Her journey takes place during the day. When she arrives, the clock reads 11. Fred leaves at the same time as Sophie. Fred's journey is 2 hours shorter than Sophie's. What time does the clock show when Fred arrives?"

In more than half the cases, information deduced by the participants when solving these problems was added unintentionally to the statement. In the case of the problem mentioned above, for example, they could be convinced—wrongly—that they had read: "Fred arrived 2 hours before Sophie" (an inference made because Fred and Sophie left at the same time, but Fred's journey took 2 hours less, which is factually true but constitutes an alteration to what the statement indicated).

"We have shown that when solving specific problems, participants have the illusion of having read sentences that were never actually presented in the statements, but were linked to unconscious deductions made when reading the statements. They become confused in their minds with the sentences they actually read," explains Hippolyte Gros, former post-doctoral fellow at UNIGE's Faculty of Psychology and Educational Sciences, lecturer at CYU, and first author of the study.

Invoking memories to understand reasoning

In addition, the experiments showed that the participants with the false memories were only those who had discovered the shortest strategy, thus revealing their unconscious reasoning that had enabled them to find this resolution shortcut. On the other hand, the others, who had operated in more stages, were unable to "enrich" their memory because they had not carried out the corresponding reasoning.

"This work can have applications for learning mathematics. By asking students to recall statements, we can identify their mental representations and therefore the reasoning they used when solving the problem, based on the presence or absence of false memories in their restitution," explains Emmanuel Sander, full professor at the UNIGE's Faculty of Psychology and Educational Sciences, who directed this research.

It is difficult to access mental constructs directly. Doing so indirectly, by analyzing memorization processes, could lead to a better understanding of the difficulties encountered by students in solving problems, and provide avenues for intervention in the classroom.

Provided by University of Geneva

Explore further

Feedback to editors

Saturday Citations: Teen seals photobomb research site; cell phones are safe; serotonin and emotional resilience

17 hours ago

Pottery shards provide insight into the lives and trade networks of enslaved people in the Cayman Islands

Nanoscale silver exhibits intrinsic self-healing abilities without external intervention

21 hours ago

Two astronauts are left behind in space as Boeing's troubled capsule returns to Earth empty

Just how rare is a rare-colored lobster? Scientists say answer could be under the shell

Massive merger: Study reveals evidence for origin of supermassive black hole at galaxy's center

Sep 6, 2024

Neolithic bones reveal isolated Yersinia pestis infections, not pandemics

New quantum error correction method uses 'many-hypercube codes' while exhibiting beautiful geometry

Solving the side effect problem of siRNA drugs for genetic disease treatment

Researchers advance new class of quantum critical metal that could advance electronic devices

Relevant physicsforums posts, difficult to understand the solution provided in the video (travelling salesman problem), questions regarding kurepa's conjecture, can higher degree nested radicals be simplified.

Sep 4, 2024

Raising to the power of 0 or 1

Calculate new height of truncated cone.

Sep 3, 2024

Scalars, Vectors, Matrices,Tensors, Holors....

More from General Math

Related Stories

Drawings of mathematical problems predict their resolution

Mar 7, 2024

Have a vexing problem? Sleep on it.

Oct 17, 2019

Expert mathematicians stumped by simple subtractions

Jul 10, 2019

Study: Cognitive flexibility enhances mathematical reasoning

Nov 29, 2022

Research reveals cuttlefish can form false memories, too

Jul 17, 2024

A new method for boosting the learning of mathematics

Dec 23, 2019

Recommended for you

Virtual learning linked to rise in chronic absenteeism, study finds

Sep 5, 2024

Mathematicians model a puzzling breakdown in cooperative behavior

Mathematicians debunk GPS assumptions to offer improvements

Aug 28, 2024

Framework for solving parabolic partial differential equations could guide computer graphics and geometry processing

AI tools like ChatGPT popular among students who struggle with concentration and attention

Researchers find academic equivalent of a Great Gatsby Curve in science mentorships

Aug 27, 2024

Let us know if there is a problem with our content

Use this form if you have come across a typo, inaccuracy or would like to send an edit request for the content on this page. For general inquiries, please use our contact form . For general feedback, use the public comments section below (please adhere to guidelines ).

Please select the most appropriate category to facilitate processing of your request

Thank you for taking time to provide your feedback to the editors.

Your feedback is important to us. However, we do not guarantee individual replies due to the high volume of messages.

E-mail the story

Your email address is used only to let the recipient know who sent the email. Neither your address nor the recipient's address will be used for any other purpose. The information you enter will appear in your e-mail message and is not retained by Phys.org in any form.

Newsletter sign up

Get weekly and/or daily updates delivered to your inbox. You can unsubscribe at any time and we'll never share your details to third parties.

More information Privacy policy

Donate and enjoy an ad-free experience

We keep our content available to everyone. Consider supporting Science X's mission by getting a premium account.

E-mail newsletter

PENGEMBANGAN MODEL PEDAGOGI DIGITAL DALAM PEMBELAJARAN MATEMATIKA TERINTEGRASI COMPUTATIONAL THINKING UNTUK MENINGKATKAN KEMAMPUAN PROBLEM SOLVING SISWA SEKOLAH MENENGAH PERTAMA

Vita Nova Anwar, - (2024) PENGEMBANGAN MODEL PEDAGOGI DIGITAL DALAM PEMBELAJARAN MATEMATIKA TERINTEGRASI COMPUTATIONAL THINKING UNTUK MENINGKATKAN KEMAMPUAN PROBLEM SOLVING SISWA SEKOLAH MENENGAH PERTAMA. S3 thesis, Universitas Pendidikan Indonesia.

Baca Full Text klik disini

ABSTRAK Vita Nova Anwar (2024). Pengembangan Model Pedagogi Digital dalam Pembelajaran Matematika Terintegrasi Computational Thinking untuk Meningkatkan Kemampuan Problem Solving Siswa SMP Penggunaan teknologi yang melibatkan keterampilan computational thinking merupakan kualifikasi yang diperlukan pada abad 21 ini. Computational thinking erat kaitannya dengan pembelajaran matematika. Dalam memecahkan masalah matematika yang kompleks penting untuk mengikuti langkah-langkah penyelesaian masalah sesuai tahapan computational thinking. Sehingga diperlukan model pembelajaran yang sesuai untuk mendukung hal tersebut. Penelitian ini bertujuan untuk mengembangkan model pedagogi digital dalam pembelajaran matematika terintegrasi computational thinking untuk meningkatkan kemampuan problem solving siswa SMP. Penelitian ini adalah penelitian pengembangan yang mengikuti model Plomp meliputi preliminary research, prototyping phase, dan assesment phase yang diuraikan secara deskriptif. Penelitian dilaksanakan pada dua sekolah SMP di kota Padang yang melibatkan 56 orang siswa kelas VIII. Aktivitas computational thinking yang dikembangkan dalam pembelajaran matematika terdiri dari aktivitas langsung dan aktivitas digital yang berbantukan teknologi. Instrumen penelitian adalah lembar validasi, lembar penilaian kepraktisan oleh guru, dan soal tes kemampuan problem solving. Hasil uji validitas menunjukkan bahwa dari segi konten, bahasa, penyajian dan kegrafikan sudah memenuhi kriteria valid dan sangat valid. Hasil uji praktikalitas memenuhi kriteria sangat praktis. Hasil uji efektivitas menunjukkan bahwa terdapat peningkatan kemampuan problem solving siswa. ABSTRACT Vita Nova Anwar (2024). Development of a Digital Pedagogical Model on Integration of Computational Thinking in Mathematics Learning to Improve Students' Problem Solving Abilities The use of technology involving computational thinking skills is a required qualification today. Computational thinking is closely related to mathematics learning. In solving complex mathematical problems, it is important to follow the problem solving steps according to the stages of computational thinking. So an appropriate learning model is needed to support this. This research aims to develop a digital pedagogy model in mathematics learning integrated with computational thinking to improve problem solving abilities of junior high school students. This research is development research that follows the Plomp model including preliminary research, prototyping phase, and assessment phase which are described descriptively. The research was carried out at two schools in Padang, involving 56 students in grade VIII. The research instruments were a validation sheet, a practicality assessment sheet by the teacher, and problem solving ability test questions. The results of the validity test show that in terms of content, language, presentation and graphics it meets the valid and very valid criteria. The results of the practicality test carried out are very practical criteria. The results of the effectiveness test show that there is an increase in students' problem solving abilities.

Actions (login required)

• Search term Advanced Search Citation Search
• Individual login
• Institutional login

Dynamic scheduling of hybrid flow shop problem with uncertain process time and flexible maintenance using NeuroEvolution of Augmenting Topologies

Yarong Chen

College of Mechanical and Electronic Engineering, Wenzhou University, Wenzhou, China

Contribution: Data curation, Funding acquisition, Resources, Supervision, Validation, Writing - original draft

Junjie Zhang

Contribution: ​Investigation, Methodology, Visualization, Writing - original draft

Corresponding Author

Mudassar Rauf

• [email protected]
• orcid.org/0000-0002-2325-9512

Correspondence

Mudassar Rauf, College of Mechanical and Electronic Engineering, Wenzhou University, Room A601b, Building No.6, Wenzhou, Zhejiang, China.

Email: [email protected]

Contribution: Conceptualization, Formal analysis, Resources, Supervision, Validation, Writing - review & editing

Jabir Mumtaz

Contribution: Formal analysis, Methodology, Resources, Visualization, Writing - review & editing

Shenquan Huang

Contribution: Data curation, Methodology, Project administration, Software, Visualization

A hybrid flow shop is pivotal in modern manufacturing systems, where various emergencies and disturbances occur within the smart manufacturing context. Efficiently solving the dynamic hybrid flow shop scheduling problem (HFSP), characterised by dynamic release times, uncertain job processing times, and flexible machine maintenance has become a significant research focus. A NeuroEvolution of Augmenting Topologies (NEAT) algorithm is proposed to minimise the maximum completion time. To improve the NEAT algorithm's efficiency and effectiveness, several features were integrated: a multi-agent system with autonomous interaction and centralised training to develop the parallel machine scheduling policy, a maintenance-related scheduling action for optimal maintenance decision learning, and a proactive scheduling action to avoid waiting for jobs at decision moments, thereby exploring a broader solution space. The performance of the trained NEAT model was experimentally compared with the Deep Q-Network (DQN) and five classical priority dispatching rules (PDRs) across various problem scales. The results show that the NEAT algorithm achieves better solutions and responds more quickly to dynamic changes than DQN and PDRs. Furthermore, generalisation test results demonstrate NEAT's rapid problem-solving ability on test instances different from the training set.

1 INTRODUCTION

The hybrid flow shop scheduling problem (HFSP) is extensively applied in chemical, textile, steel, and semiconductor industries and is recognised as an NP-hard problem [ 1 ]. HFSP exhibits greater complexity compared to traditional flow shop scheduling problems, as it integrates parallel machines and flow shop scheduling issues [ 2 ]. In the context of smart manufacturing, the complexity and uncertainty of manufacturing systems have significantly escalated due to the demand for multi-variety, small-batch, and personalised product [ 3 ]. Addressing the HFSP effectively, especially considering dynamic events, has thus become a central focus of production scheduling research. The dynamic hybrid flow shop scheduling problem (DHFSP) is deemed more valuable compared to the classic job shop problem since it includes most of the scheduling problems associated with high-mix, low-volume production [ 4 ]. In addition, DHFSP tackles the uncertainties that naturally exist in the production environment, including dynamic demand, machine unavailability, and uncertain process time [ 5 ]. Consequently, this paper focuses on DHFSP with uncertain process times, dynamic job arrivals, and flexible maintenance. There are four major challenges in solving the presented DHFSP. First, uncertainty in job processing times makes it difficult to predict and plan the scheduling accurately, increasing the complexity of the scheduling problem. Second, jobs arriving at different times dynamically add another layer of complexity, requiring real-time adjustments to the schedule. Third, the need for flexible and often unpredictable machine maintenance schedules complicates the decision-making process. Thus, incorporating uncertain process times, dynamic job arrivals, and flexible maintenance significantly complicates decision-making in DHFSP. Fourth, rapid and efficient decision-making is crucial, especially with the advancements in Industry 4.0, where quick responses to changing conditions are essential.

In recent decades, dynamic machine scheduling has been the subject of extensive research [ 6 - 9 ]. Three primary dynamic scheduling methods identified in the literature are completely reactive scheduling (CRS) [ 10 ], predictive reactive scheduling (PRS), and robust scheduling (RS) [ 11 ]. CRS methods, exemplified by dispatching rules like the shortest processing time (SPT) rule [ 12 ] and the First in First out rule [ 13 ] offer rapid solution generation. However, their short-term focus often produces suboptimal solutions for complex, long-term scheduling problems. PRS, a rescheduling approach, initially creates a complete schedule using heuristic or meta-heuristic methods. Upon encountering dynamic disturbances, a new schedule based on the current state is generated to maintain the stability of the manufacturing system. Commonly used meta-heuristic algorithms include genetic algorithm (GA) [ 14 , 15 ], particle swarm optimisation [ 16 - 18 ] and ant colony optimisation [ 19 - 21 ]. While PRS can achieve near-optimal solutions, it may incur high preparatory costs due to potential underestimation of deviations between new and original scheduling solutions. RS anticipates disturbances, adopts preemptive measures, and generates solutions that consider current conditions and potential disruptions.

For HFSP with frequent dynamic events, the regular application of PRS-generated solutions may negatively impact production process stability. While the RS method ensures manufacturing robustness, it often compromises scheduling effectiveness. From the standpoint of real-time response to frequent dynamic changes, CRS is preferable. However, traditional dispatching rules, tailored for specific dynamic scenarios, lack the ability to self-adjust. With the advancement of machine learning, reinforcement learning (RL) methods have become increasingly popular for learning optimal scheduling policies based on the production state at the decision moment [ 22 ].

Over the past few decades, RL-based dynamic scheduling methods have garnered significant attention in research. These methods typically employ agents to select different actions, often scheduling rules, at various decision moments to minimise the impact of uncertainty on the objective value. Presently, there are two primary approaches: classical RL and deep reinforcement learning (DRL), both of which have been effectively applied in machine scheduling problems. Classical RL methods, utilising algorithms like Q-learning [ 23 , 24 ] and Sarsa [ 25 ], address Markov decision process problems but necessitate predefined Q-table sizes. Despite their notable achievements, classical RL methods encounter the challenge of state explosion, especially in manufacturing scenarios with discrete state spaces where the state space can be vast, making the maintenance of a large Q-table impractical. Moreover, classical RL struggles with unknown state spaces. To address the limitations of individual RL models, researchers have proposed ensemble RL methods which combine multiple learning algorithms to improve robustness and performance. Liu et al. [ 24 ] proposed a Q-learning based ensemble evolutionary algorithm for FSP which leverage the evolutionary algorithm's exploration capabilities and RL's policy optimisation. In contrast, DRL has significantly advanced in handling sequential decision-making in complex, discrete state spaces [ 26 ]. It leverages artificial neural networks (ANN) as approximators for value functions, allowing the direct input of state feature vectors into an ANN to evaluate the q -value of each potential action, thus addressing the state explosion issue. However, traditional DRL models, such as Actor-Critic (AC) and Deep Q-Network (DQN), often require extensive experimental validation and significant manual effort.

NeuroEvolution of Augmenting Topologies (NEAT) algorithm, proposed by Stanley et al. [ 27 ] is a GA used for evolving ANN. Unlike conventional neural network algorithms that only optimise the weights, the NEAT algorithm simultaneously optimises both the topology (structure) and the weights of the neural network [ 23 ]. This dual optimisation allows the algorithm to adapt better to dynamic hybrid flow shop scheduling complexities. Its ability to evolve and adjust the neural network structure makes it robust in handling unpredictable changes in job arrivals, process times, and maintenance schedules [ 28 ]. NEAT integrates the strengths of both RL (for learning optimal policies through interaction with the environment) and evolutionary algorithms (for exploring and optimising complex solution spaces). This hybrid approach leverages the benefits of both methodologies to effectively address the scheduling problem. This integration facilitates automated neural network design and reduces manual labour. Thus, NEAT requires less work than various problem-specific DRL approaches. Therefore, this paper emphasises the NEAT algorithm for addressing the HFSP, considering dynamic release times, uncertain job processing times, and flexible preventive maintenance. Table  1 summarises the distinctions between the proposed method and existing RL-based approaches for dynamic HFSP, covering aspects such as dynamic events, optimisation objectives, and algorithms.

• Abbreviations: CMA, Cooperative memetic algorithm; DDPG, deep deterministic policy gradient; DQND, DQN with diminishing greedy rate; EC, energy consumption; GCN, graph convolutional network; GIN, graph isomorphism network; MA, Multi-agent; MS, Maximum completion time or makespan; OSP, Optimal scheduling period; PFSPNet-AC, permutation flow-shop scheduling problem network-actor critic; PPO, proximal policy optimisation training algorithm; SA, Single agent; TT, Total tardiness.

It can be concluded from Table  1 that researchers have often considered only a single aspect of dynamic events, such as machine maintenance, uncertain processing times, or dynamic job release, with limited studies addressing multiple dynamic events simultaneously. Han et al. [ 30 ] first studied the RL-based HFSP scheduling method while considering the single dynamic event. Wang et al. [ 32 ] introduced a cooperative memetic algorithm with an RL strategy for energy-aware distributed hybrid flow shop scheduling problems. Dong et al. [ 33 ] explored the application of DRL and graph isomorphic networks in reducing the delay criteria for permutation flow shop scheduling issues. However, studies considering multiple dynamic events concurrently are scarce, with a notable example being Lang et al. [ 29 ] who developed the NEAT algorithm to address the two-stage HFSP incorporating product family set-up times. Consequently, this paper addresses the dynamic scheduling of hybrid flow shops, integrating flexible preventive maintenance for machines and multiple dynamic events such as dynamic job release and uncertain processing times.

Moreover, most existing studies concentrate on single-agent frameworks. For instance, Yan et al. [ 34 ] applied DRL to address the distributed permutation flow shop scheduling problem with flexible preventive maintenance, while Pan et al. [ 35 ] developed an efficient optimisation algorithm using DRL to tackle the permutation flow shop scheduling problem, aiming to minimise the maximum completion time. Conversely, research on multi-agent RL remains scarce. Zhang et al. [ 34 ] proposed a deep multi-agent graph method for flexible job shop scheduling problem (FJSP) with the objective of minimising completion time. Jing et al. [ 37 ] developed a multi-agent graph convolutional network-based algorithm for FJSP, aiming to reduce maximum completion time. Liu et al. [ 31 ] introduced a hybrid approach combining a GA with a multi-agent DRL system to manage HFSP, taking into account factors such as worker fatigue and skill levels. This study proposes a learning policy tailored for multi-agent systems, facilitating centralised training and distributed execution, which is particularly suited to the nature of parallel machines.

In summary, research on RL algorithms for HFSP has yielded noteworthy outcomes, laying a solid groundwork for this paper's investigations. Given the NEAT algorithm's adaptability in neural network topology and weight parameters, this study applies NEAT to the dynamic HFSP while considering flexible preventive maintenance of machines, dynamic job release, and uncertain job processing times. The aim of this paper is to provide real-time and intelligent scheduling solutions for the dynamic HFSP. The main contributions of this paper are as follows: (1) A learning strategy for multi-agent systems that integrates centralised training with distributed execution is proposed to enhance scheduling efficiency. (2) A maintenance decision-learning scheduling action, based on maintenance thresholds and aimed at leveraging the flexibility of machine preventive maintenance, is introduced. (3) A scheduling action for the dynamic release of jobs is proposed, which avoids selecting jobs at specific decision points to broaden the solution space.

The structure of the remainder of this paper is as follows: Section  2 details the problem addressed and its Mixed Integer Programming (MIP) model. Section  3 provides an in-depth discussion of the proposed NEAT algorithm. Section  4 presents an analysis of experiments and results from the application of the proposed algorithm, including a comparison with other algorithms. Section  5 concludes the paper and outlines future research directions.

2 PROBLEM DESCRIPTION AND MATHEMATICAL MODEL

The HFSP with dynamic events examined in this paper involves n dynamically release jobs J i ( i  = 1, 2, …, n ) processed across K ( K  ≥ 2) stages, where each stage k contains m k ( m k  ≥ 1; k  = 1, 2, …, K ) machines, with at least one stage featuring parallel machines. The model incorporates flexible preventive maintenance based on actual production needs, stipulating that a machine's continuous processing time cannot exceed the maintenance threshold ( UT ), with the maintenance duration denoted as t m . The objective of this study is to minimise the maximum completion time. The completion of a job at a stage or the release of a new job triggers a decision-making process aimed at optimising the objective value. This is achieved by strategically assigning the dynamically released jobs to the machines to ensure efficient scheduling. The decision of this problem includes that how to assign the jobs to the machine at each stage and determine the sequence of jobs in each machine. In addition, the decision of when to conduct preventive maintenance is also needed to determine.

The assumptions made in this study are as follows: (1) Each machine can process only one job at a time. (2) The processing time for a job is consistent across all machines at stage k . (3) Once the processing sequence of jobs at stage 1 is established, the sequence on machines at subsequent stages follows accordingly. (4) The setup time for machines and the transportation time of jobs between adjacent stages are disregarded. To construct the MIP model for the problem under study, symbols and variables are defined to characterise the problem as presented in Table  2 .

Equation ( 1 ) aims to minimise the maximum completion time. Equation ( 2 ) specifies how to calculate this maximum completion time. Equation ( 3 ) specifies that each job is assigned to one machine at one stage. Equations ( 4 ) and ( 5 ) ensure that each job is processed by only one position of one machine at any given stage. Equations ( 6 ) ensures that if there is a job in the next position on the same machine, then there must be a job in the previous position. Equations ( 7 ) and ( 8 ) establish the start and completion times for jobs at the first processing stage. Equation ( 10-11 ) determines that the cumulative continuous processing times of the first position of each machine at any given stage. Equations ( 10 ) and ( 11 ) determines that the cumulative continuous processing times on a machine do not exceed the maintenance threshold. Equations ( 12 ) determines that the cumulative continuous processing times on a machine do not exceed the maintenance threshold. Equations ( 13 ) and ( 14 ) determine the start and completion times for the job J i ${J}_{i}$ at stage k $k$ . Equation ( 15 ) ensures that the same machine is constrained in terms of backward and forward relationships.

To demonstrate the problem addressed in this paper, consider the following example: There are six jobs ( n  = 6) to be processed through three stages ( K  = 3), with the number of machines at each stage being { m 1 , m 2 , m 3 } = {2, 1, 2}. The release times of the jobs are R  = {1, 1, 1, 3, 2, 1}, and the processing times at each stage are P  = {[1, 1, 1], [3, 2, 3], [3, 5, 2], [5, 1, 5], [5, 3, 5]}. The maintenance threshold is set at UT  = 10, and the maintenance time is t m  = 2. In one of the solution scenarios illustrated by a Gantt chart in Figure  1 , the processing sequence at stage 1 is PS  = [ J 1 , J 2 , J 5 , J 6 , J 4 , J 3 ]. At stage 2, jobs are processed based on the first-come-first-served (FCFS) rule. At decision moment 2, job J 1 finishes at stage 1 and immediately starts at stage 2. By decision moment 4, jobs J 2 and J 5 finish at stage 1; however, with only one machine ( M 21 ) is available at stage 2, job J 2 is processed first in line with the established sequence PS. Following this approach for subsequent stages leads to a solution with a maximum completion time of 23.

Gantt chart of a solution for an example.

The accuracy of the mathematical model was verified by CPLEX in python. A simple verification exercise was performed to ensure the correctness and credibility of the mathematical model. Several small test problems consisting of three machines, six jobs, and two stages were generated. The first stage comprised two machines, while the second stage had one machine. We programmed the mathematical model in the CPLEX in python to solve these test problems. The solution obtained by the mathematical model was compared with the enumeration method. The experimental results showed that the solutions from the model were consistent with those obtained by the enumeration method, thereby validating the mathematical model.

3 THE PROPOSED NEAT-BASED ALGORITHM

Stanley et al. first introduced the NEAT algorithm [ 27 , 38 ]. It is based on GA, which explores acceptable artificial neural network structures and optimal parameters for a specific machine-learning problem [ 26 ]. The standard GA employs a search method based on the principles of natural evolution. It starts by randomly creating an initial population of solution candidates, often known as genomes. Subsequently, the algorithm introduces mutations and crossovers to the random pairs of solutions to create new ones during multiple generations until a termination condition is satisfied, such as reaching a maximum number of generations [ 39 ]. GA-based NEAT has similarities with RL techniques due to its properties [ 23 ]. Both approaches do not rely on labelled training data. Instead, they create learning signals using fitness or reward functions. These functions assess the quality of the output produced by any artificial neural network solution. The NEAT algorithm enhances the weight parameters and the topology of neural networks, unlike traditional DRL algorithms such as DQN and AC [ 29 , 40 ]. NEAT utilises evolutionary algorithms to refine neural network structure and connection weights, addressing complex dynamic decision-making challenges. As a combination of GA and DRL, NEAT employs the population dynamics, crossover, and mutation processes of GA to evolve neural networks [ 41 ]. This research utilises the NEAT algorithm to tackle the DHFSP. The sorting of jobs at stage 1 is considered a dynamic decision-making process. A multi-agent system employing centralised training with distributed execution is developed to facilitate the learning of the scheduling policy, where the sorting results of jobs at stage 1 are used as selection constraints for subsequent stages. The NEAT algorithm and the scheduling model are implemented separately and are only linked through an input/output interface as shown in Figure  2 . Eight state features are extracted from the production environment as inputs, and six dispatching rules are defined as actions for the NEAT algorithm to minimise the maximum completion time.

NEAT algorithm and scheduling environment interactions.

3.1 Framework of the proposed NEAT-based algorithm

The process begins with parameter initialisation, followed by the construction of a neural network that interacts with the environment to derive fitness values. The initial population consists of simple networks, usually including input and output nodes with randomly assigned weights and no hidden nodes. During the process of evolution, mutations introduce more nodes and connections, increasing the network structure's complexity. The fitness function is determined by simulating the scheduling process using each neural network. The most successful neural networks are chosen using an elitist method to generate the next generation. Offspring networks are produced via crossover and mutation, progressively evolving to yield an agent with the optimal scheduling policy. This methodology is illustrated in Figure  3 . Based on the references [ 2 , 29 ], an interaction module between the agent and the hybrid flow shop system environment is crafted, with the corresponding pseudocode shown in Algorithm  1 . The iteration process continues for several generations until convergence is achieved through evaluation, selection, crossover, and mutation.

The framework of the proposed NEAT algorithm.

Algorithm 1. Pseudocode for Agent and environment interaction module.

For each neural network P:

Initialisation state S o , the number of stages K , processing sequence table PS  = {∅}

 For each decision moment t d

  For k  = 1 to K do

   If current stage k  = 1 and there are idle machines in stage k do

    While sequentially apply agents of idle machines do

     Update the instantaneous state S t d ${S}_{{t}_{d}}$ , and execute the action a t d ${a}_{{t}_{d}}$ , place the selected job into the machining sequence list PS

    End While

   If current stage k  ≠ 1 and there are idle machines in stage k do

    While sequentially select idle machines do

     Assign jobs to the machines according to the sequence in the list PS

If all jobs have been completed do

   Calculate the maximum completion time C max

Output fitness value Fitness = 1 C max $\text{Fitness}=\frac{1}{{C}_{\max }}$

3.2 Genetic encoding

The NEAT algorithm employs a unique genetic encoding method to represent the structure of the neural network. Genetic encoding involves modelling neural networks as genomes, which are essentially lists of genes. This encoding allows the NEAT algorithm to evolve both the structure (topology) and the weights of neural networks over successive generations. Each neural network is encoded as a genome consisting of two main parts: the node gene and the connection gene. Node genes represent the neurons in the neural network. Each node gene contains information about the node type and its unique identifier. Connection genes represent synaptic connections between neurons. Each connection gene includes the input node, the output node, the weight of the connection, the enable bit (indicating whether the connection is active), and an innovation number. The genetic encoding used for NEAT is designed to allow corresponding genes to be easily combined during crossover events. Genomes are linear representations of network connectivity and include the information of the two node genes being connected. This design facilitates the evolutionary process, enabling the NEAT algorithm to explore and optimise neural network structures efficiently.

The mutation and crossover operations are performed at each iteration in the NEAT algorithm. Mutation introduces random changes to a genome, which is essential for introducing new genetic material into the population and enabling the exploration of the solution space [ 27 ]. Two types of mutations are shown in Figure  4 . Add connection mutation adds a new connection between two previously unconnected nodes with a random weight, enabling the network to form new pathways and potentially discover new features and relationships in the data as shown in Figure  4a . Add node mutation splits an existing connection by inserting a new node. The original connection is disabled, and two new connections are added as shown in Figure  4b . This allows the network to evolve new layers and more complex behaviours. Crossover is a genetic operation used in NEAT to combine the genetic material of two parent genomes to produce offspring [ 42 ]. NEAT uses innovation numbers to align matching genes correctly, ensuring that similar structures from different parents are combined effectively as shown in Figure  5 . If a gene is present in one parent but not the other, it can be inherited from the more fit parent or randomly included/excluded.

The mutation operations of the NEAT algorithm.

The crossover operations of the NEAT algorithm.

3.3 State representation

The agent creates a scheduling action based on the state features, which need to accurately represent the current system state, encompassing both job and machine information. As these state features form the sole input for generating scheduling actions, they must encapsulate data crucial for evaluating these actions. In alignment with the action space and considering the fundamental details of certain jobs, eight state features ( ft 1 , ft 2 , …, ft 8 ) have been adopted from literature [ 43 - 45 ] and given in Table  3 . State features ft 1 , ft 2 , …, ft 5 represent job information in the buffer, while state features ft 6 , ft 7 , ft 8 represent machine and decision-related state information in the hybrid flow shop at stage 1. The dimensions of all state features are 1 +  n  ∗ 4 +  m 1  ∗ 3 (where m 1 is the number of machines at stage 1 and n is the number of jobs).

The symbols in Table  3 are described as follows. n BF represents the number of jobs in the buffer pool set ( BF ) at stage 1. Q i represents the quantity of job J i in the job buffer pool at stage 1. T i r ${T}_{i}^{r}$ represents the time interval between job J i and its release time. T 1 c represents the processing time of the job being processed by machine M 1 c ( c  = 1, 2, …, m 1 ) at stage 1. T 1 c a ${T}_{1c}^{a}$ represents the processing time of the job being processed by machine M 1 c at stage 1. U 1 c r ${U}_{1c}^{r}$ represents the remaining maintenance threshold for machine M 1 c at stage 1.

3.4 Action presentation

The action is used to select a job from the buffer and assign it to a machine to be processed during scheduling decisions. The optimal policy of job selection in different states directly affects the final training effect and the quality of the solution. Therefore, the action should include effective actions for various production states. Six scheduling actions as follows were designed based on reference.

The action in the scheduling process involves selecting a job from the buffer and assigning it to a machine for processing. The effectiveness of job selection across different states plays a crucial role in the final training outcome and the quality of the solution. Thus, it is important that the action set encompasses effective responses to various production scenarios. As recommended by Liu et al. [ 2 ], six scheduling actions were designed to accommodate a range of production states, ensuring a comprehensive strategy for dynamic scheduling decisions. The dispatching rules for job sequence contain: ( a 1 ) FIFO; ( a 2 ) SPT; ( a 3 ) longest processing time (LPT); ( a 4 ) shortest total processing time (STPT); ( a 5 ) longest total processing time (LTPT); ( a 6 ) Skip. The processing time of SPT and LPT rules is the processing time of job at the stage 1. STPT and LTPT mean the shortest and longest total processing time (TPT) of job at all stages, and T P T = ∑ k = 1 K p i k $TPT=\sum \nolimits_{k=1}^{K}{p}_{ik}$ . If more than one job matches the dispatching rules of the job sequence, calculate the batch waste B 1 c i = U 1 c r − p i 1 $\left({B}_{1ci}={U}_{1c}^{r}-{p}_{i1}\right)$ of selected jobs based on the remaining threshold value U 1 c r ${U}_{1c}^{r}$ on machine M 1 c , and select the job with the smallest batch waste. If there are multiple jobs, randomly select one of job J i . Set the following constraints for several special situations: (1) When there are no jobs in the waiting queue, the agent can only choose scheduling action a 6 . (2) When a new job releases but there are no idle machines, select scheduling action a 6 . (3) When there are jobs in the waiting queue and all machines are idle, scheduling action a 6 cannot be selected.

3.5 Reward design

The optimisation objective of this paper is to minimise the maximum completion time ( C max ), while the NEAT algorithm aims to learn the scheduling policy by maximising global rewards or fitness functions. Thus, the fitness function for NEAT is designed as Fitness = 1 C max $\text{Fitness}=\frac{1}{{C}_{\max }}$ , where C max = max C T i , K ${C}_{\max }=\max \,\left\{{CT}_{i,K}\right\}$ , and CT i , K is the completion time of the last processing stage of job J i . Maximising the fitness function in this manner is equivalent to minimising the maximum completion time, aligning the algorithm's objectives with the paper's optimisation goal.

4 EXPERIMENTAL DESIGN AND RESULT ANALYSIS

4.1 experimental design.

The algorithms were developed in PyCharm and executed on a PC with a Windows 10 operating system, a 2.9 GHz CPU, and 16 GB of RAM to assess the computational performance. The hybrid flow shop simulation environment, along with the NEAT agent model and priority dispatching rules (PDRs), was constructed using Python 3.9. Additionally, the development of the DQN agent model was implemented using the Pytorch module in Python 3.9. Following the methodology described by Yuksel [ 41 ], the job processing time p ik , release time r i , and the number of machines at each stage m k for experimental problems are generated using a uniform distribution. The problems are categorised into three scales based on the number of stages K and n number of jobs: small scale ( K  = 2, n  = 10), medium scale ( K  = 4, n  = 50), large scale ( K  = 6, n  = 100). For each scale, three different sets of instances are created to serve as the training set. The specific range of parameter values is as follows: p ik and r i are distributed uniformly in the interval [1, 5], m k is distributed uniformly in the interval [1, 2], UT is set to 10 and t m is set to 2.

The performance of the algorithm highly depends upon the correct selection of parameters [ 46 , 47 ]. Therefore, to get optimal solutions for a specific problem, pre-experiments were conducted using the problem instances with K  = 6 and n  = 100 as example. The Taguchi method was employed to investigate the effect of population size and evaluation generations on the performance of the NEAT algorithm. Each parameter was considered at three levels: population size {100, 150, 200} and generations {15, 20, 25}. The response value from each experiment was converted into a signal-to-noise (S/N) ratio. The convergence curves of fitness values for a population size of 100 are presented in Figure  6 . Analysis of Figure  6 and S/N ratios indicates that all three schemes reached satisfactory fitness values near the 10th generation, beyond which the improvement in fitness values became stable and gradual, with the number of iterations as the termination condition. Consequently, an optimal level of each key parameters is shown in Table  4 . For a fair comparison, each algorithm was run 10 times on each problem instance to account for variability in performance. The mean and standard deviation values of the results were recorded to provide a reliable assessment of each algorithm's performance. The experimental setup was kept consistent to avoid discrepancies arising from different computational efficiencies. The parameters of the other compared algorithms were also fine-tuned using the Taguchi method as shown in Table  4 .

Convergence curves for NEAT algorithm under different evolutionary generations.

4.2 Results analysis

This section assesses the NEAT scheduling method's performance using the maximum completion time ( C max ) and the average computation time T s R $\left({T}_{s}^{R}\right)$ for generating scheduling decisions. The trained model was applied to solve test problems mirroring the training set's distribution. For each scale, three sets of instance problems were generated and solved 10 times to ensure reliability. The results in Table  5 reveal that for all three problem scales, the NEAT algorithm consistently achieved optimal C max values. This success is attributed to the NEAT algorithm's ability to select the most appropriate scheduling actions based on the real-time state of the scheduling problem, thereby minimising C max . Specifically, for small-scale problems, SPT and STPT rules can also find near-optimal solutions due to the small solution space. However, the increased complexity of medium and large-scale problems hinders these scheduling rules from finding near-optimal solutions. In contrast, trained NEAT and DQN models can identify the most suitable real-time scheduling actions. NEAT outperforms the scheduling rules and DQN due to its adaptive neural network topology. The NEAT model, tailored through training, fits the problem more accurately than DQN's fixed neural network structure. Therefore, the NEAT algorithm obtains a better C max than other compared algorithms. Regarding the response time (SD) for a single decision, scheduling rules are the fastest due to their straightforward judgement and selection processes based on preset rules, requiring no complex computations. Although NEAT and DQN have longer response times, they operate within the e-05 s range, reflecting the more complex matrix calculations performed by their neural network models. With its adaptive topology that modifies the neural network's nodes and connections, the NEAT algorithm results in a non-fully connected network that demands fewer computational resources than DQN's fully connected network, thus slightly reducing the SD compared to DQN.

• Note : σ —standard deviation, avg—average value, SD—response time for a single decision, AD—computation time for all decisions.

Figure  7 illustrates a box plot comparing the maximum completion time C max and AD is required to derive the optimal scheduling strategy across three different scales using various algorithms. This visualisation helps in assessing the variability and distribution of both C max and AD among the algorithms, providing insights into their performance and efficiency in solving the scheduling problem at different complexity levels. Figure  7 demonstrates that the NEAT-based algorithm exhibits superior robustness. Figure  7a,b show that for small and medium-scale problems, both NEAT and DQN algorithms show better robustness and achieve near-optimal solutions, outperforming the SPT and LPT scheduling rules. Figure  7c indicates that for large-scale problems, the NEAT algorithm maintains the highest robustness and closest to optimal solutions, followed by DQN and SPT rules, with LPT rules trailing behind. This performance is attributed to the evolutionary and training processes of NEAT and DQN, which yield robust agent models capable of adapting to environmental changes, particularly for small and medium-sized problems. SPT rules, which prioritise jobs based on processing time, demonstrate moderately lower robustness, while other scheduling rules, which select jobs based on current states and objective values, show even less robustness. The NEAT algorithm's ability to explore a more exhaustive solution space through neural network and weight parameter evolution contributes to its optimal robustness in large-scale scenarios. DQN's fixed neural network structure, evolving only in terms of weight parameters, limits its robustness in comparison. The inherent limitations of scheduling rules in solving large-scale problems further contribute to their lower robustness.

Box plots of different algorithms at three different scales.

Regarding computational time (AD), scheduling rules consistently require the least time across all scales, followed by NEAT and DQN. The longer computation times for DQN are due to its fixed, fully connected neural network structure, necessitating extensive forward feedback and backpropagation calculations, which may not always align well with the scheduling problem. Conversely, NEAT's evolutionary algorithm approach tailors the neural network to the problem's complexity, resulting in a more straightforward network structure than DQN and, thus shorter computation times. Scheduling rules exhibit minimal response times, bypassing the complex calculations and iterative processes inherent in neural network-based methods.

Further, the statistical method, specifically the one-tailed t -test is adopted to confirm the statistical difference between the NEAT algorithm and DQN. The level of significance was set at 0.05 [ 48 ]. If NEAT was significantly worse than, statistically equivalent to, or significantly better than the comparative algorithms, the optimisation results are displayed as ‘−’, ‘∼’, or ‘+’, respectively [ 49 ]. The results are presented in Table  6 . Table  6 shows that for medium and large problem instances, the NEAT algorithm consistently outperforms the DQN algorithm. While for small problem instances, the performance of NEAT is similar to that of DQN. However, as discussed above, the NEAT algorithm demands fewer resources and thus provides a rapid response, as evident from the SD and AD values in Table  5 . Therefore, the NEAT algorithm offers superior performance compared to DQN when considering the C max , SD, and AD values.

4.3 Generalisation performance analysis

Generalisation performance is a crucial metric for evaluating DRL algorithms, assessing the ability to effectively apply learnt knowledge and experience to unfamiliar environments and achieve favourable outcomes [ 41 ]. To assess the generalisation performance of the NEAT scheduling method, parameters from the large-scale problem used in training were expanded to create diverse generalisation test problems. The details of these parameters are listed in Table  7 . For each generalisation test problem, 10 sets of instances were randomly generated, and each set was solved 10 times using the trained NEAT model and trained DQN model. The result, also known as win percentage (win %, representing the algorithm's superiority ratio over the 10 sets of instances in the generalisation test problem) is shown in Table  8 . This approach helps evaluate how well the NEAT algorithm adapts to changes and maintains its performance in scenarios not encountered during the training phase.

• Note : NEAT-DQN win: percentage of NEAT winning over DQN.

The data presented in Table  7 shows that the NEAT-based algorithm maintains a win rate of nearly 80% compared with DQN across all test problems. This indicates that the trained NEAT model provides better results than the trained DQN model. The reason is that since the NEAT algorithm considers the evolution of the neural network topology structure, it results in a more robust model with better generalisation to unknown environments or data.

It can be seen from the above results that NEAT algorithm outperformed DQN and other dispatching rules. The reason lies in NEAT's ability to evolve both the structure and weights of neural networks, its robustness to dynamic and uncertain environments, improved learning and generalisation capabilities, and integration of evolutionary strategies contribute to its superior performance over DQN in DHFSP. These advantages allow NEAT to develop more adaptable, efficient, and effective models tailored to the specific needs of the scheduling problem.

5 CONCLUSIONS

This paper addresses the dynamic scheduling problem in a hybrid flow shop environment, aiming to minimise the maximum completion time. It introduces a multi-agent NEAT RL approach tailored for dynamic decision-making at the initial stage, accounting for dynamic job release times, uncertain processing times, and flexible machine maintenance. Multiple features were incorporated to enhance the efficiency and effectiveness of the NEAT algorithm. A multi-agent system was designed to facilitate autonomous interaction and centralised training, aiding in the development of a scheduling policy for parallel machines. Additionally, a maintenance-specific scheduling action was introduced to optimise maintenance decisions. The performance of the proposed method is compared with that of DQN RL and five PDRs. The comparative experiments demonstrate the NEAT algorithm's superior ability to deliver effective scheduling solutions and promptly adapt to dynamic changes. Moreover, the generalisation experiments have showcased the NEAT model's strong adaptability, confirming its effectiveness in handling new, previously unseen scheduling problems within a defined parameter range. The NEAT algorithm, with its unique ability to concurrently optimise the neural network structure and weight parameters, has demonstrated superior performance in generating effective scheduling solutions and adapting rapidly to dynamic changes in the manufacturing environment.

Future research should aim to enhance the complexity management of scheduling in actual production settings. This involves developing an efficient approach to define state features that accurately represent the complex hybrid flow shop environment with minimal redundancy. Exploring multi-objective optimisation methods that align more closely with real-world conditions is crucial, particularly in developing DRL models and algorithms suited for multi-objective optimisation scheduling challenges.

AUTHOR CONTRIBUTIONS

Yarong Chen : Data curation; funding acquisition; resources; supervision; validation; writing – original draft. Junjie Zhang : Investigation; methodology; visualization; writing – original draft. Mudassar Rauf : Conceptualization; formal analysis; resources; supervision; validation; writing – review & editing. Jabir Mumtaz : Formal analysis; methodology; resources; visualization; writing – review & editing. Shenquan Huang : Data curation; methodology; project administration; software; visualization.

ACKNOWLEDGEMENTS

This work has been supported by the National Natural Science Foundation of China, Grant No. 51705370 and Basic Scientific Research Project of Wenzhou City, Grant No. G20240020 & G2023036.

CONFLICT OF INTEREST STATEMENT

All authors declare that they have no conflict of interest or financial conflicts to disclose.

PERMISSION TO REPRODUCE MATERIALS FROM OTHER SOURCES

Open research, data availability statement.

Data available on request from the authors.

• 1 Marichelvam, M.K. , Tosun, Ö. , Geetha, M. : Hybrid monkey search algorithm for flow shop scheduling problem under makespan and total flow time . Appl. Soft Comput. 55 , 82 – 92 ( 2017 ). https://doi.org/10.1016/j.asoc.2017.02.003 10.1016/j.asoc.2017.02.003 Web of Science® Google Scholar
• 2 Liu, Y. , et al.: Integration of deep reinforcement learning and multi-agent system for dynamic scheduling of re-entrant hybrid flow shop considering worker fatigue and skill levels . Robot. Comput. Integrated Manuf. 84 , 102605 ( 2023 ). https://doi.org/10.1016/j.rcim.2023.102605 10.1016/j.rcim.2023.102605 Google Scholar
• 3 Xie, J. , et al.: A hybrid genetic tabu search algorithm for distributed flexible job shop scheduling problems . J. Manuf. Syst. 71 , 82 – 94 ( 2023 ). https://doi.org/10.1016/j.jmsy.2023.09.002 10.1016/j.jmsy.2023.09.002 Google Scholar
• 4 Xie, J. , et al.: Review on flexible job shop scheduling . IET Collab. Intell. Manuf. 1 ( 3 ), 67 – 77 ( 2019 ). https://doi.org/10.1049/iet-cim.2018.0009 10.1049/iet-cim.2018.0009 Google Scholar
• 5 Ding, L. , et al.: Multi-policy deep reinforcement learning for multi-objective multiplicity flexible job shop scheduling . Swarm Evol. Comput. 87 , 101550 ( 2024 ). https://doi.org/10.1016/j.swevo.2024.101550 10.1016/j.swevo.2024.101550 Google Scholar
• 6 Liu, X. , et al.: Parallel machine scheduling with stochastic release times and processing times . Int. J. Prod. Res. 59 ( 20 ), 6327 – 6346 ( 2021 ). https://doi.org/10.1080/00207543.2020.1812752 10.1080/00207543.2020.1812752 Google Scholar
• 7 Abedi, M. , et al.: Bi-objective optimisation for scheduling the identical parallel batch-processing machines with arbitrary job sizes, unequal job release times and capacity limits . Int. J. Prod. Res. 53 ( 6 ), 1680 – 1711 ( 2015 ). https://doi.org/10.1080/00207543.2014.952795 10.1080/00207543.2014.952795 Web of Science® Google Scholar
• 8 Chen, Y.-Y. , et al.: Makespan minimization for scheduling on two identical parallel machines with flexible maintenance and nonresumable jobs . J. Ind. Prod. Eng. 38 ( 4 ), 271 – 284 ( 2021 ). https://doi.org/10.1080/21681015.2021.1883131 10.1080/21681015.2021.1883131 Google Scholar
• 9 Luo, S. , Zhang, L. , Fan, Y. : Real-time scheduling for dynamic partial-no-wait multiobjective flexible job shop by deep reinforcement learning . IEEE Trans. Autom. Sci. Eng. 19 ( 4 ), 3020 – 3038 ( 2022 ). https://doi.org/10.1109/tase.2021.3104716 10.1109/TASE.2021.3104716 Google Scholar
• 10 Li, K. , et al.: An effective MCTS-based algorithm for minimizing makespan in dynamic flexible job shop scheduling problem . Comput. Ind. Eng. 155 , 107211 ( 2021 ). https://doi.org/10.1016/j.cie.2021.107211 10.1016/j.cie.2021.107211 Web of Science® Google Scholar
• 11 Jiang, Y. , et al.: Efficient robust scheduling of integrated electricity and heat systems: a direct constraint tightening approach . IEEE Trans. Smart Grid 12 ( 4 ), 3016 – 3029 ( 2021 ). https://doi.org/10.1109/tsg.2021.3066449 10.1109/TSG.2021.3066449 Google Scholar
• 12 Xu, K. , et al.: Reinforcement learning-based multi-objective of two-stage blocking hybrid flow shop scheduling problem . Processes 12 ( 1 ), 51 ( 2024 ). https://doi.org/10.3390/pr12010051 10.3390/pr12010051 Google Scholar
• 13 Schumacher, C. , Buchholz, P. : Scheduling algorithms for a hybrid flow shop under uncertainty . Algorithms 13 ( 11 ), 277 ( 2020 ). https://doi.org/10.3390/a13110277 10.3390/a13110277 Google Scholar
• 14 Rahman, H.F. , Sarker, R. , Essam, D. : A real-time order acceptance and scheduling approach for permutation flow shop problems . Eur. J. Oper. Res. 247 ( 2 ), 488 – 503 ( 2015 ). https://doi.org/10.1016/j.ejor.2015.06.018 10.1016/j.ejor.2015.06.018 Web of Science® Google Scholar
• 15 Luo, J. , et al.: GPU based parallel genetic algorithm for solving an energy efficient dynamic flexible flow shop scheduling problem . J. Parallel Distr. Comput. 133 , 244 – 257 ( 2019 ). https://doi.org/10.1016/j.jpdc.2018.07.022 10.1016/j.jpdc.2018.07.022 Google Scholar
• 16 Tang, D. , et al.: Energy-efficient dynamic scheduling for a flexible flow shop using an improved particle swarm optimization . Comput. Ind. 81 , 82 – 95 ( 2016 ). https://doi.org/10.1016/j.compind.2015.10.001 10.1016/j.compind.2015.10.001 Web of Science® Google Scholar
• 17 Ramezanian, R. , Sanami, S.F. , Nikabadi, M.S. : A simultaneous planning of production and scheduling operations in flexible flow shops: case study of tile industry . Int. J. Adv. Manuf. Technol. 88 ( 9-12 ), 2389 – 2403 ( 2017 ). https://doi.org/10.1007/s00170-016-8955-z 10.1007/s00170-016-8955-z Google Scholar
• 18 Gholizadeh, H. , Chaleshigar, M. , Fazlollahtabar, H. : Robust optimization of uncertainty-based preventive maintenance model for scheduling series-parallel production systems (real case: disposable appliances production) . ISA Trans. 128 , 54 – 67 ( 2022 ). https://doi.org/10.1016/j.isatra.2021.11.041 10.1016/j.isatra.2021.11.041 PubMed Google Scholar
• 19 Qin, W. , Zhang, J. , Song, D. : An improved ant colony algorithm for dynamic hybrid flow shop scheduling with uncertain processing time . J. Intell. Manuf. 29 ( 4 ), 891 – 904 ( 2018 ). https://doi.org/10.1007/s10845-015-1144-3 10.1007/s10845-015-1144-3 Web of Science® Google Scholar
• 20 Shen, C. , Chen, Y. : Blocking flow shop scheduling based on hybrid ant colony optimization . Int. J. Simulat. Model. 19 ( 2 ), 313 – 322 ( 2020 ). https://doi.org/10.2507/ijsimm19-2-co7 10.2507/IJSIMM19-2-CO7 Google Scholar
• 21 Zhang, Y.Q. , Zhang, H. : Dynamic scheduling of blocking flow-shop based on multi-population ACO algorithm . Int. J. Simulat. Model. 19 ( 3 ), 529 – 539 ( 2020 ). https://doi.org/10.2507/ijsimm19-3-co15 10.2507/IJSIMM19-3-CO15 Google Scholar
• 22 Wang, L. , Pan, Z. , Wang, J. : A review of reinforcement learning based intelligent optimization for manufacturing scheduling . Complex Syst. Model. Simulat. 1 ( 4 ), 257 – 270 ( 2021 ). https://doi.org/10.23919/csms.2021.0027 10.23919/CSMS.2021.0027 CAS Google Scholar
• 23 Zhang, Z.-Q. , et al.: A Q-learning-based hyper-heuristic evolutionary algorithm for the distributed flexible job-shop scheduling problem with crane transportation . Expert Syst. Appl. 234 , 121050 ( 2023 ). https://doi.org/10.1016/j.eswa.2023.121050 10.1016/j.eswa.2023.121050 Google Scholar
• 24 Liu, F. , et al.: Ensemble evolutionary algorithms equipped with Q-learning strategy for solving distributed heterogeneous permutation flowshop scheduling problems considering sequence-dependent setup time . IET Collab. Intell. Manuf. 6 ( 1 ), e12099 ( 2024 ). https://doi.org/10.1049/cim2.12099 10.1049/cim2.12099 Web of Science® Google Scholar
• 25 Chen, R. , et al.: A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem . Comput. Ind. Eng. 149 , 106778 – 106789 ( 2020 ). https://doi.org/10.1016/j.cie.2020.106778 10.1016/j.cie.2020.106778 Web of Science® Google Scholar
• 26 Yang, S. , Xu, Z. , Wang, J. : Intelligent decision-making of scheduling for dynamic permutation flowshop via deep reinforcement learning . Sensors 21 ( 3 ), 1019 ( 2021 ). https://doi.org/10.3390/s21031019 10.3390/s21031019 Google Scholar
• 27 Stanley, K.O. , Miikkulainen, R. : Evolving neural networks through augmenting topologies . Evol. Comput. 10 ( 2 ), 99 – 127 ( 2002 ). https://doi.org/10.1162/106365602320169811 10.1162/106365602320169811 PubMed Web of Science® Google Scholar
• 28 Sarti, S. , Ochoa, G. : A NEAT Visualisation of Neuroevolution Trajectories . Springer Google Scholar
• 29 Lang, S. , et al.: NeuroEvolution of augmenting topologies for solving a two-stage hybrid flow shop scheduling problem: a comparison of different solution strategies . Expert Syst. Appl. , 172 ( 2021 ) Google Scholar
• 30 Han, W. , Guo, F. , Su, X. : A reinforcement learning method for a hybrid flow-shop scheduling problem . Algorithms 12 ( 11 ), 222 ( 2019 ). https://doi.org/10.3390/a12110222 10.3390/a12110222 Web of Science® Google Scholar
• 31 Liu, Y. , et al.: Agent-based simulation and optimization of hybrid flow shop considering multi-skilled workers and fatigue factors . Robot. Comput. Integrated Manuf. 80 , 102478 ( 2023 ). https://doi.org/10.1016/j.rcim.2022.102478 10.1016/j.rcim.2022.102478 Web of Science® Google Scholar
• 32 Wang, J.-J. , Wang, L. : A cooperative memetic algorithm with learning-based agent for energy-aware distributed hybrid flow-shop scheduling . IEEE Trans. Evol. Comput. 26 ( 3 ), 461 – 475 ( 2022 ). https://doi.org/10.1109/tevc.2021.3106168 10.1109/TEVC.2021.3106168 Google Scholar
• 33 Dong, Z. , et al.: Minimizing the late work of the flow shop scheduling problem with a deep reinforcement learning based approach . Appl. Sci.-Basel 12 ( 5 ), 2366 ( 2022 ). https://doi.org/10.3390/app12052366 10.3390/app12052366 CAS Google Scholar
• 34 Yan, Q. , Wu, W. , Wang, H. : Deep reinforcement learning for distributed flow shop scheduling with flexible maintenance . Machines 10 ( 3 ), 210 ( 2022 ). https://doi.org/10.3390/machines10030210 10.3390/machines10030210 Google Scholar
• 35 Pan, Z. , et al.: Deep reinforcement learning based optimization algorithm for permutation flow-shop scheduling . IEEE Trans. Emerg. Top. Comput. Intell. 7 ( 4 ), 983 – 994 ( 2023 ). https://doi.org/10.1109/tetci.2021.3098354 10.1109/TETCI.2021.3098354 Google Scholar
• 36 Gui, Y. , et al.: Dynamic scheduling for flexible job shop using a deep reinforcement learning approach . Comput. Ind. Eng. 180 , 109255 ( 2023 ). https://doi.org/10.1016/j.cie.2023.109255 10.1016/j.cie.2023.109255 Google Scholar
• 37 Jing, X. , et al.: Multi-agent reinforcement learning based on graph convolutional network for flexible job shop scheduling . J. Intell. Manuf. 35 ( 1 ), 75 – 93 ( 2024 ). https://doi.org/10.1007/s10845-022-02037-5 10.1007/s10845-022-02037-5 Google Scholar
• 38 Stanley, K.O. , Miikkulainen, R. : Efficient evolution of neural network topologies . In: Proceedings of the 2002 Congress on Evolutionary Computation (CEC'02) ( 2002 ) 10.1109/CEC.2002.1004508 Google Scholar
• 39 Mumtaz, J. , et al.: Solving line balancing and AGV scheduling problems for intelligent decisions using a Genetic-Artificial bee colony algorithm . Comput. Ind. Eng. 189 , 109976 ( 2024 ). https://doi.org/10.1016/j.cie.2024.109976 10.1016/j.cie.2024.109976 Google Scholar
• 40 Liang, W. , et al.: Bi-dueling DQN enhanced two-stage scheduling for augmented surveillance in smart EMS . IEEE Trans. Ind. Inf. 19 ( 7 ), 8218 – 8228 ( 2023 ). https://doi.org/10.1109/tii.2022.3216295 10.1109/TII.2022.3216295 Google Scholar
• 41 Yuksel, M.E. : Agent-based evacuation modeling with multiple exits using NeuroEvolution of Augmenting Topologies . Adv. Eng. Inf. 35 , 30 – 55 ( 2018 ). https://doi.org/10.1016/j.aei.2017.11.003 10.1016/j.aei.2017.11.003 Google Scholar
• 42 Khamesian, S. , Malek, H. : Hybrid self-attention NEAT: a novel evolutionary self-attention approach to improve the NEAT algorithm in high dimensional inputs . Evolving Syst. 15 ( 2 ), 489 – 503 ( 2024 ). https://doi.org/10.1007/s12530-023-09510-3 10.1007/s12530-023-09510-3 Google Scholar
• 43 Yang, S. , Xu, Z. : Intelligent scheduling and reconfiguration via deep reinforcement learning in smart manufacturing . Int. J. Prod. Res. 60 ( 16 ), 4936 – 4953 ( 2021 ). https://doi.org/10.1080/00207543.2021.1943037 10.1080/00207543.2021.1943037 Google Scholar
• 44 Park, I.-B. , Park, J. : Scalable scheduling of semiconductor packaging facilities using deep reinforcement learning . IEEE Trans. Cybern. 53 ( 6 ), 3518 – 3531 ( 2023 ). https://doi.org/10.1109/tcyb.2021.3128075 10.1109/TCYB.2021.3128075 PubMed Google Scholar
• 45 Yang, S. , Wang, J. , Xu, Z. : Real-time scheduling for distributed permutation flowshops with dynamic job arrivals using deep reinforcement learning . Adv. Eng. Inf. 54 , 101776 ( 2022 ). https://doi.org/10.1016/j.aei.2022.101776 10.1016/j.aei.2022.101776 Google Scholar
• 46 Fu, Y. , et al.: Multiobjective scheduling of energy-efficient stochastic hybrid open shop with brain storm optimization and simulation evaluation . IEEE Trans. Syst. Man. Cybern. Syst. 54 ( 7 ), 4260 – 4272 ( 2024 ). https://doi.org/10.1109/tsmc.2024.3376292 10.1109/TSMC.2024.3376292 Google Scholar
• 47 Rauf, M. , et al.: Integrated planning and scheduling of multiple manufacturing projects under resource constraints using raccoon family optimization algorithm . IEEE Access 8 , 151279 – 151295 ( 2020 ). https://doi.org/10.1109/access.2020.2971650 10.1109/ACCESS.2020.2971650 Google Scholar
• 48 Ma, X. , et al.: A multi-objective scheduling and routing problem for home health care services via brain storm optimization . Complex Syst. Model. Simulat. 3 ( 1 ), 32 – 46 ( 2023 ). https://doi.org/10.23919/csms.2022.0025 10.23919/CSMS.2022.0025 Google Scholar
• 49 Fu, Y. , et al.: Stochastic multi-objective integrated disassembly-reprocessing-reassembly scheduling via fruit fly optimization algorithm . J. Clean. Prod. 278 , 123364 ( 2021 ). https://doi.org/10.1016/j.jclepro.2020.123364 10.1016/j.jclepro.2020.123364 Google Scholar

Volume 6 , Issue 3

September 2024

Information

Log in to Wiley Online Library

Change password, your password must have 10 characters or more:.

• a lower case character, 
• an upper case character, 
• a special character 

Password Changed Successfully

Your password has been changed

Create a new account

Forgot your password.

Enter your email address below.

Please check your email for instructions on resetting your password. If you do not receive an email within 10 minutes, your email address may not be registered, and you may need to create a new Wiley Online Library account.

Request Username

Can't sign in? Forgot your username?

Enter your email address below and we will send you your username

If the address matches an existing account you will receive an email with instructions to retrieve your username

A MIP-heuristic approach for solving a bi-objective optimization model for integrated production planning of sugarcane and energy-cane

• Original Research
• Published: 02 September 2024

Cite this article

• Gilmar Tolentino 1   na1 ,
• Antônio Roberto Balbo   ORCID: orcid.org/0000-0002-4512-0140 1   na1 ,
• Sônia Cristina Poltroniere 1   na1 ,
• Angelo Aliano Filho   ORCID: orcid.org/0000-0002-5088-134X 2   na1 &
• Helenice de Oliveira Florentino   ORCID: orcid.org/0000-0003-2740-8826 3   na1  

This paper proposes a modeling and solution approach for the integrated planning of the planting and harvesting of sucrose cane and energy-cane considering multiple harvesters. An integer linear bi-objective optimization model is proposed, which seeks to find a trade-off between the maximization of the production volumes of sucrose and fiber and the minimization of the operational costs. The model considers the technical constraints of the mill, such as the milling capacity and meeting the monthly demand. A MIP-heuristic based on relax-and-fix and fix-and-optimize strategies with exact decomposition is appropriately proposed to determine approximations to Pareto optimal solutions to this problem. These approximations are used as incumbents for a branch-and-bound tree to generate potentially Pareto optimal solutions. The results reveal that the MIP-heuristic efficiently solves the problem for real and semi-random instances, generating approximate solutions with a reduced error and a reasonable computational effort. Moreover, the different solutions quantify the trade-off between cost and production volume, opening up the possibility of increasing sucrose and fiber content or decreasing the costs of solutions found. Thus, the proposed bi-objective approach, the solution technique and the different Pareto optimal solutions obtained can assist mill managers in making better decisions in sugarcane production.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

An Optimization Model of Sugarcane Harvesting with Fixed and Variable Costs Approximated by Fourier and Cubic Functions

A multiple objective methodology for sugarcane harvest management with varying maturation periods.

Exact and heuristic methods to solve a bi-objective problem of sustainable cultivation

More details, see the Gurobi manual at https://www.gurobi.com/documentation/current/refman/heuristics.html.

Agarwal, A. K. (2007). Biofuels (alcohols and biodiesel) applications as fuels for internal combustion engines. Progress in Energy and Combustion Science, 33 (3), 233–271.

Article   Google Scholar  

Akartunali, K., & Miller, A. J. (2009). A heuristic approach for big bucket multi-level production planning problems. European Journal of Operational Research, 193 (2), 396–411. https://doi.org/10.1016/j.ejor.2007.11.033

Aliano, A. F., Cantane, D. R., Isler, P. R., & Florentino, H. O. (2023). An integrated multi-objective mathematical model for sugarcane harvesting considering cumulative degree-days. Expert Systems with Applications, 232 , 120881.

Aliano, A. F., Melo, T., & Pato, M. V. (2021). A bi-objective mathematical model for integrated planning of sugarcane harvesting and transport operations. Computers & Operations Research, 134 , 105419.

Aliano, A. F., Moretti, A. C., Pato, M. V., & de Oliveira, W. A. (2021). An exact scalarization method with multiple reference points for bi-objective integer linear optimization problems. Annals of Operations Research, 296 (1), 35–69.

Aliano, F. A., de Oliveira, W. A., & Melo, T. (2022). Multi-objective optimization for integrated sugarcane cultivation and harvesting planning. European Journal of Operational Research, 309 (1), 330–344.

Beraldi, P., Ghiani, G., Grieco, A., & Guerriero, E. (2008). Rolling-horizon and fix-and-relax heuristics for the parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs. Computers & Operations Research, 35 (11), 3644–3656.

Bezanson, J., Edelman, A., Karpinski, S., & Shah, V. B. (2017). Julia: A fresh approach to numerical computing. SIAM Review, 59 (1), 65–98.

Bigaton, A., Danelon, A. F., Bressan, G., Silva, H. J. T., & Rosa, J. H. M. (2017). Previsão de custos do setor sucroenergético na região centro-sul do Brasil: safra 2017/18. Revista IPecege, 3 (3), 65–70.

Bruzzone, A. A. G., Anghinolfi, D., Paolucci, M., & Tonelli, F. (2012). Energy-aware scheduling for improving manufacturing process sustainability: A mathematical model for flexible flow shops. CIRP Annals - Manufacturing Technology, 61 (1), 459–462.

Calija, V., Higgins, A. J., Jackson, P. A., Bielig, L. M., & Coomans, D. (2001). An operations research approach to the problem of the sugarcane selection. Annals of Operations Research, 108 (1–4), 123–142.

Cárdenas-Barrón, L. E., Melo, R. A., & Santos, M. C. (2021). Extended formulation and valid inequalities for the multi-item inventory lot-sizing problem with supplier selection. Computers and Operations Research, 130 , 105234.

Cheavegatti-Gianotto, A., de Abreu, H. M. C., Arruda, P., Bespalhok Filho, J. C., Burnquist, W. L., Creste, S., di Ciero, L., Ferro, J. A., et al. (2011). Sugarcane ( saccharum x officinarum ): A reference study for the regulation of genetically modified cultivars in brazil. Tropical Plant Biology, 4 , 62–89.

Chu, S., & Majumdar, A. (2012). Opportunities and challenges for a sustainable energy future. Nature, 488 (7411), 294–303.

Cunha, J. O., Mateus, G. R., & Melo, R. A. (2022). A hybrid heuristic for capacitated three-level lot-sizing and replenishment problems with a distribution structure. Computers and Industrial Engineering, 173 , 108698. https://doi.org/10.1016/j.cie.2022.108698

Danna, E., Rothberg, E., & Pape, C. L. (2005). Exploring relaxation induced neighborhoods to improve MIP solutions. Mathematical Programming, 102 , 71–90.

Dunning, I., Huchette, J., & Lubin, M. (2017). Jump: A modeling language for mathematical optimization. SIAM Review, 59 (2), 295–320.

Ehrgott, M., & Wiecek, M. M. (2005). Multiobjective programming. Multiple Criteria Decision Analysis: State of the Art Surveys, 78 , 667–708.

Google Scholar  

Etemadnia, H., Goetz, S. J., Canning, P., & Tavallali, M. S. (2015). Optimal wholesale facilities location within the fruit and vegetables supply chain with bimodal transportation options: An lp-mip heuristic approach. European Journal of Operational Research, 244 (2), 648–661.

Farias, M. E. A., Martins, M. F., & Cândido, G. A. (2021). Agenda 2030 e energias renováveis: Sinergias e desafios para alcance do desenvolvimento sustentável. Research, Society and Development, 10 (17), e13101723867.

Ferreira, D., Morabito, R., & Rangel, S. (2009). Solution approaches for the soft drink integrated production lot sizing and scheduling problem. European Journal of Operational Research, 196 (2), 697–706. https://doi.org/10.1016/j.ejor.2008.03.035

Fischetti, M., & Lodi, A. (2003). Local branching. Mathematical Programming, 98 , 23–47.

Florentino, H. O., Irawan, C., Aliano, F. A., Jones, D. F., Cantane, D. R., & Nervis, J. J. (2018). A multiple objective methodology for sugarcane harvest management with varying maturation periods. Annals of Operations Research, 267 (1), 153–177.

Florentino, H. O., Jones, D. F., Irawan, C., Ouelhadj, D., Khosravi, B., & Cantane, D. R. (2020). An optimization model for combined selecting, planting and harvesting sugarcane varieties. Annals of Operations Research, 314 , 451–469.

Florentino, H. O., & Pato, M. V. (2014). A bi-objective genetic approach for the selection of sugarcane varieties to comply with environmental and economic requirements. Journal of the Operational Research Society, 65 (6), 842–854.

García-Segura, T., Penadés-Plà, V., & Yepes, V. (2018). Sustainable bridge design by metamodel-assisted multi-objective optimization and decision-making under uncertainty. Journal of Cleaner Production, 202 , 904–915.

Giagkiozis, I., & Fleming, P. J. (2015). Methods for multi-objective optimization: An analysis. Information Sciences, 293 , 338–350.

Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2022). https://www.gurobi.com .

Helber, S., & Sahling, F. (2010). A fix-and-optimize approach for the multi-level capacitated lot sizing problem. International Journal of Production Economics, 123 (2), 247–256.

Higgins, A. (2006). Scheduling of road vehicles in sugarcane transport: A case study at an Australian sugar mill. European Journal of Operational Research, 170 (3), 987–1000.

Higgins, A., Antony, G., Sandell, G., Davies, I., Prestwidge, D., & Andrew, B. (2004). A framework for integrating a complex harvesting and transport system for sugar production. Agricultural Systems, 82 (2), 99–115.

Higgins, A. J., & Muchow, R. C. (2003). Assessing the potential benefits of alternative cane supply arrangements in the Australian sugar industry. Agricultural Systems, 76 (2), 623–638.

Higgins, A. J., & Postma, S. (2004). Australian sugar mills optimise siding rosters to increase profitability. Annals of Operations Research, 128 (1–4), 235–249.

James, R. J. W., & Almada-Lobo, B. (2011). Single and parallel machine capacitated lotsizing and scheduling: New iterative MIP-based neighborhood search heuristics. Computers and Operations Research, 38 (12), 1816–1825. https://doi.org/10.1016/j.cor.2011.02.005

Jena, S. D., & Poggi, M. (2013). Harvest planning in the Brazilian sugar cane industry via mixed integer programming. European Journal of Operational Research, 230 (2), 374–384.

Junqueira, R., & Morabito, R. (2019). Modeling and solving a sugarcane harvest front scheduling problem. International Journal of Production Economics, 213 , 150–160. https://doi.org/10.1016/j.ijpe.2019.03.009

Kaab, A., Sharifi, M., Mobli, H., Nabavi-Pelesaraei, A., & Chau, K. (2019). Use of optimization techniques for energy use efficiency and environmental life cycle assessment modification in sugarcane production. Energy, 181 , 1298–1320.

Kaewtrakulpong, K., Takigawa, T., Koike, M., Hasegawa, H., & Bahalayodhin, B. (2008). Truck allocation planning for cost reduction of mechanical sugarcane harvesting in Thailand an application of multi-objective optimization. Journal of the Japanese Society of Agricultural Machinery, 70 (2), 62–71.

Lamsal, K., Jones, P. C., & Thomas, B. W. (2017). Sugarcane harvest logistics in Brazil. Transportation Science, 51 (2), 771–789.

Liebman, M., & Dyck, E. (1993). Crop rotation and intercropping strategies for weed management. Ecological Applications, 3 (1), 92–122.

Lima, C., Balbo, A. R., Homem, T. P. D., & Florentino, H. O. (2017). A hybrid approach combining interior-point and branch-and-bound methods applied to the problem of sugar cane waste. Journal of the Operational Research Society, 68 (2), 147–164.

Matsuoka, S. & Rubio, L. C. S. (2019). Energy cane: A sound alternative of a bioenergy crop for tropics and subtropics. In Sugarcane Biofuels , pp. 39–66. Springer.

Matsuoka, S., dos Santos, E. G. D. & Tomazela, A. L. (2017). Free Fiber Level Drives Resilience and Hybrid Vigor in Energy Cane. LAP LAMBERT Academic Publishing.

Matsuoka, S., Rubio, L., Tomazela, A., & Santos, E. (2016). A evoluçao do proálcool. AgroANALYSIS, 36 (1), 29–30.

Miettinen, K. (1999). Nonlinear Multiobjective Optimization, vol. 12. Springer.

Milan, E. L., Fernandez, S. M., & Aragones, L. M. P. (2006). Sugar cane transportation in Cuba, a case study. European Journal of Operational Research, 174 (1), 374–386.

Muchow, R. C., Higgins, A. J., Rudd, A. V., & Ford, A. W. (1998). Optimising harvest date in sugar production: A case study for the Mossman mill region in Australia: II. sensitivity to crop age and crop class distribution. Field Crops Research, 57 (3), 243–251.

Nervis, J. J. (2015). Simulação para a otimização da colheita da cana-de-açúcar.

Nikulin, Y., Miettinen, K., & Mäkelä, M. M. (2012). A new achievement scalarizing function based on parameterization in multiobjective optimization. OR Spectrum, 34 (1), 69–87.

Pathumnakul, S., & Nakrachata-Amon, T. (2015). The applications of operations research in harvest planning: A case study of the sugarcane industry in Thailand. Journal of Japan Industrial Management Association, 65 (4E), 328–333.

Poltroniere, S. C., Aliano, F. A., Caversan, A. S., Balbo, A. R., & Florentino, H. O. (2021). Integrated planning for planting and harvesting sugarcane and energy-cane for the production of sucrose and energy. Computers and Electronics in Agriculture . https://doi.org/10.1016/j.compag.2020.105956

Pongpat, P., Mahmood, A., Ghani, H. U., Silalertruksa, T., & Gheewala, S. H. (2023). Optimization of food-fuel-fibre in biorefinery based on environmental and economic assessment: The case of sugarcane utilization in Thailand. Sustainable Production and Consumption, 37 , 398–411. https://doi.org/10.1016/j.spc.2023.03.013

Pornprakun, W., Sungnul, S., Kiataramkul, C., & Moore, E. J. (2019). Determining optimal policies for sugarcane harvesting in Thailand using bi-objective and quasi-newton optimization methods. Advances in Difference Equations, 2019 , 1–15.

Qiu, M., Meng, Y., Chen, J., Chen, Y., Li, Z., & Li, J. (2023). Dual multi-objective optimisation of the cane milling process. Computers & Industrial Engineering, 179 , 109146. https://doi.org/10.1016/j.cie.2023.109146

Ramos, R. P., Isler, P. R., Florentino, H. O., Jones, D., & Nervis, J. J. (2016). An optimization model for the combined planning and harvesting of sugarcane with maturity considerations. African Journal of Agricultural Research, 11 (40), 3950–3958.

Santoro, E., Soler, E. M., & Cherri, A. C. (2017). Route optimization in mechanized sugarcane harvesting. Computers and Electronics in Agriculture, 141 , 140–146.

Santos, J. A. (2022). Análise do sistema de energia fotovoltaica do Instituto Federal do Ceará-Campus Maracanaú e sua colaboração na redução da emissão de CO2. Available on: http://conexoes.ifce.edu.br/index.php/conexoes/article/view/2168 . Retrieved February 19, 2023.

Sethanan, K., & Neungmatcha, W. (2016). Multi-objective particle swarm optimization for mechanical harvester route planning of sugarcane field operations. European Journal of Operational Research, 252 (3), 969–984.

Shirvani, N., Ruiz, R., & Shadrokh, S. (2014). Cyclic scheduling of perishable products in parallel machine with release dates, due dates and deadlines. International Journal of Production Economics, 156 , 1–12.

Silva, A. F., Marins, F. A. S., & Dias, E. X. (2015). Addressing uncertainty in sugarcane harvest planning through a revised multi-choice goal programming model. Applied Mathematical Modelling, 39 (18), 5540–5558.

Toso, E. A., Morabito, R., & Clark, A. R. (2009). Lot sizing and sequencing optimisation at an animal-feed plant. Computers & Industrial Engineering, 57 (3), 813–821.

USDA: United States Department of Agriculture. (2023). Available on: https://apps.fas.usda.gov/psdonline/app/index.html#/app/advQuery . Retrieved January 31, 2023.

Usman, M., & Balsalobre-Lorente, D. (2022). Environmental concern in the era of industrialization: Can financial development, renewable energy and natural resources alleviate some load? Energy Policy, 162 , 112780.

Varshney, D., Mandade, P., & Shastri, Y. (2019). Multi-objective optimization of sugarcane bagasse utilization in an Indian sugar mill. Sustainable Production and Consumption, 18 , 96–114.

Walfrido, A. P., Luengo, C. A., Koehlinger, J., Garzone, P., & Cornacchia, G. (2008). Sugarcane energy use: The Cuban case. Energy policy, 36 (6), 2163–2181.

Download references

The authors thank to Brazilian foundations: CNPq n \(^{\textrm{o}}\) 306518/2022-8, CNPq n \(^{\textrm{o}}\) 304218/2022-7, FAPESP 2021/03039-1,FAPESP 2022/12652-1, PROPE/PROPG/UNESP/ FUNDUNESP grant 12/2022, for the financial support and language services provided.

Author information

Gilmar Tolentino, Antônio Roberto Balbo, Sônia Cristina Poltroniere, Angelo Aliano Filho and Helenice de Oliveira Florentino have contributed equally to this work.

Authors and Affiliations

Department of Mathematics, State University of Sao Paulo, Bauru, São Paulo, 17033-360, Brazil

Gilmar Tolentino, Antônio Roberto Balbo & Sônia Cristina Poltroniere

Department of Mathematics, Universidade Tecnológica Federal do Paraná, Apucarana, Paraná, 86812-460, Brazil

Angelo Aliano Filho

Department of Bioestatistics, State University of Sao Paulo, Botucatu, São Paulo, 18618-690, Brazil

Helenice de Oliveira Florentino

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Angelo Aliano Filho .

Ethics declarations

Conflict of interest..

The authors declare to have no Conflict of interest.

Ethical approval.

This article does not contain any studies with human participants or animals performed by any of the authors.

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary Information

Below is the link to the electronic supplementary material.

Supplementary file 1 (pdf 109 KB)

Rights and permissions.

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Tolentino, G., Balbo, A.R., Poltroniere, S.C. et al. A MIP-heuristic approach for solving a bi-objective optimization model for integrated production planning of sugarcane and energy-cane. Ann Oper Res (2024). https://doi.org/10.1007/s10479-024-06229-5

Download citation

Received : 06 May 2023

Accepted : 16 August 2024

Published : 02 September 2024

DOI : https://doi.org/10.1007/s10479-024-06229-5

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Multi-objective optimization
• Sugarcane production
• OR in agriculture
• MIP-heuristic

Advertisement

• Find a journal
• Publish with us
• Track your research