e-journal

A Branch and Bound Algorithm for Cyclic Scheduling of Timed Petri Nets

---

A timed Petri net (TPN) has been widely used for modeling, scheduling, and analyzing discrete event dynamic systems. This study examines cyclic scheduling problems of a TPN to minimize the cycle time especially for automated manufacturing systems. Appropriate token routing at each conflict place canmake
a TPN repeat an identical firing sequence.We propose a systematic procedure to transform a TPN with such cyclic token routing into an equivalent timed event graph (TEG) for which the cycle time
and firing schedules can be evaluated by a linear programming (LP). Based on the transformation procedure, we develop an efficient branch and bound algorithmto solve the scheduling problem.
A partial solution is defined as a partial token route that has only a subset of token routes for determining the complete schedule. The lower bound of a partial solution is determined by the cycle
time of a TEG that has the partial token route. The cycle time of a TEG with an additional token route for a new partial solution is computed by a dual-simplex algorithm which avoids solving the
LP completely again. A dynamic branching strategy that prevents unnecessary branching for the scheduling decision is also proposed. We demonstrate the computational efficiency through intensive
experiments of cluster tools and robotic flow shops.
Note to Practitioners—There are many systems which repeat an identical task sequence such as manufacturing systems, transportation systems, and robotic systems. Maximizing the throughput of such a system by optimizing the cyclic task sequence, which is called a cyclic scheduling problem, has been an
important problem. In order to deal with cyclic scheduling problems, this paper uses a timed Petri net (TPN) which is a graphical modeling tool for discrete event dynamic systems. As the size of a
TPN model increases, the computational complexity of the cyclic scheduling problem exponentially increases due to the combinatorial nature of sequencing problems. Therefore, an efficient
algorithm for optimal cyclic scheduling of TPNs is needed. This study proposes an efficient branch and bound algorithm which is a kind of a tree search algorithm. Several important techniques
are developed. First, a transformation procedure from a TPN to a timed event graph is developed. Second, an efficient branching rule which reduces the size of the search tree is proposed. Third,
the lower bound which evaluates the cycle time of each node in the search tree is suggested. We verify the efficiency of the algorithm through the experiments on manufacturing systems such as a cluster tool and a robotic flow shop.
Index Terms—Branch and bound algorithm, cluster tool, cyclic scheduling, timed event graph (TEG), timed Petri net (TPN).

---

Ketersediaan

Tidak ada salinan data

Informasi Detail

Judul Seri

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING

No. Panggil

-

Penerbit

New York : IEEE., 2015

Deskripsi Fisik

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, VOL. 12, NO. 1, JANUARY 2015

Bahasa

English

ISBN/ISSN

1545-5955

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

VOL. 12, NO. 1, JANUARY 2015

Subjek

TEKNIK

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Yuli/Agus

Versi lain/terkait

Lampiran Berkas

Komentar

---

Anda harus masuk sebelum memberikan komentar