Automatic Generation of Mixed Integer Programming for Scheduling Problems Based on Colored Timed Petri Nets

Andrea Veronica PORCO  Ryosuke USHIJIMA  Morikazu NAKAMURA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.2   pp.367-372
Publication Date: 2018/02/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.367
Type of Manuscript: Special Section LETTER (Special Section on Mathematical Systems Science and its Applications)
scheduling problem,  mixed integer programming,  Petri nets,  colored timed Petri net,  automatic generation,  

Full Text: PDF(486.7KB)
>>Buy this Article

This paper proposes a scheme for automatic generation of mixed-integer programming problems for scheduling with multiple resources based on colored timed Petri nets. Our method reads Petri net data modeled by users, extracts the precedence and conflict relations among transitions, information on the available resources, and finally generates a mixed integer linear programming for exactly solving the target scheduling problem. The mathematical programing problems generated by our tool can be easily inputted to well-known optimizers. The results of this research can extend the usability of optimizers since our tool requires just simple rules of Petri nets but not deep mathematical knowledge.