A Problem Solver for Scheduling Workflows in Multi-agents Systems Based on Petri Nets

Author

Fu-Shiung Hsieh ; Jim-Bon Lin

Author_Institution

Dept. of Comput. Sci. & Inf. Eng., Chaoyang Univ. of Technol., Taichung, Taiwan

fYear

2013

fDate

22-26 July 2013

Firstpage

316

Lastpage

321

Abstract

Workflow scheduling in multi-agent systems (MAS) is a challenging problem due to the computational complexity involved, distributed architecture and dependency of different agents´ workflows. How to develop a problem solver that can be applied in MAS to achieve coherent and consistent workflow schedules that can meet a customer´s order is an important issue. In this paper, we propose a solution methodology for scheduling workflows in MAS. Our solution combines the multi-agent system architecture, contract net protocol and workflow models specified by Petri nets. Our solution algorithm is developed based on transformation of workflow model to network models. A subgradient algorithm and a heuristic algorithm are applied to find the solutions. A problem solver for workflow scheduling in MAS has been implemented.

Keywords

Petri nets; computational complexity; multi-agent systems; scheduling; virtual enterprises; MAS; Petri Nets; computational complexity; contract net protocol; distributed architecture; heuristic algorithm; multiagent system architecture; subgradient algorithm; virtual enterprises; workflow models; workflow scheduling problem solver; Companies; Computer architecture; Job shop scheduling; Optimization; Processor scheduling; Schedules; muiti-agent sysytem; scheduling; workflow;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Software and Applications Conference Workshops (COMPSACW), 2013 IEEE 37th Annual

Conference_Location

Japan

Type

conf

DOI

10.1109/COMPSACW.2013.47

Filename

6605809