mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Solving flow shop problems using a forward-chaining partial-order planner
Mälardalen University, School of Innovation, Design and Engineering.
2016 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Planning is the task of putting together a sequence of actions that takes a start state to a goal state. Since planning is a crucial part of human intelligence it is also a crucial part of artificial intelligence. As with human planning there are many different ways of AI planning and many different problems to plan. This thesis aims to discover how well a specific way of AI planning performs on a specific sort of problem. The planner that was investigated is called the POPF planner which is a forward-chaining partial-order planner which is an attempt at merging two different ways of planning. This was done to see how well this relatively uncommon method of planning compares to other more traditional methods of planning such as forward-chaining planners when solving a flow shop problem. A flow shop problem is a problem regarding minimizing the idle time for a facility that contains a number of m machines that need to do n jobs. Each of the n jobs 1…n have to be processed on m machines 1…m in that order. Tests were done to see how the POPF planner performed in comparison to planners that work differently. This was done by creating a flow shop problem suitable for testing and then testing the POPF planner on the problem and comparing the results to two other planners. The other planners being the COLIN and TFD planners which both work differently from each other and the POPF planner. Suggestions were also made for how the POPF planner could potentially be improved using additional methods such as landmarks. The results of the test show that the POPF planner is better than the COLIN planner and as good if not better than the TFD planner depending on the complexity of the problem. An additional test was done using the POPStar planner that specializes in the sorts of problem that was created for testing. This POPStar planner outperformed the other planners as expected but it loses in flexibility since it cannot solve problems defined in PDDL. The final results show that the POPF planner performs on a similar level to other general planners when it comes to solving flow shop problems while still having some of the benefits of being a partial-order planner such as being more flexible than a totally-ordered planner.

Place, publisher, year, edition, pages
2016. , p. 28
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:mdh:diva-30890OAI: oai:DiVA.org:mdh-30890DiVA, id: diva2:898817
Subject / course
Computer Science
Supervisors
Examiners
Available from: 2017-10-17 Created: 2016-01-29 Last updated: 2018-01-10Bibliographically approved

Open Access in DiVA

fulltext(986 kB)25 downloads
File information
File name FULLTEXT01.pdfFile size 986 kBChecksum SHA-512
1b31ebeb6f8351422fca92c970dd4f51ae13f24ce3fc54c44fd6cbd007d2cd8c6b67db57a73dd6ca916621133a238ed9bb2cd1a633d9cd031e66150144bda96e
Type fulltextMimetype application/pdf

By organisation
School of Innovation, Design and Engineering
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 25 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 41 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf