NDLI: A heuristic approach based on the state equations of Petri nets for FMS scheduling

Content Provider	IEEE Xplore Digital Library
Author	Shih Chang Chen Mu Der Jeng
Copyright Year	1995
Description	Author affiliation: Dept. of Electr. Eng., Nat. Taiwan Ocean Univ., Keelung, Taiwan (Shih Chang Chen; Mu Der Jeng)
Abstract	The paper proposes a heuristic method based on the state equations of Petri nets for flexible manufacturing systems (FMSs) scheduling. We formulate the FMS scheduling problem as a transition firing sequence of a timed Petri net, and then generate a partial reachability graph of the net. The net is searched for the goal state, using the solutions, which are firing count vectors, of the state equation to predict the total cost from the initial state through the current state to the goal. The solutions may contain spurious solutions because a firing count loses sequence information. However the optimal solution which is the smallest makespan is always contained in them. If we eliminate the effect of spurious solutions as much as possible, this method can obtain a good near-optimal schedule. Since this heuristic approach exploits the linear characterization of the state equations, we can not only efficiently obtain a good near-optimal solution, but also evaluate the performance of the schedules. On the other hand, memory requirement is an important issue for a scheduling algorithm. If a scheduling algorithm needs a lot of memory, and even if we are able to get optimal solutions, the algorithm is still impractical for large problems. Thus, searching less states in the scheduling procedure corresponds to improving the scheduling efficiency. Therefore, the scheduling algorithm proposed in the paper contains an step to reduce the search space.
Starting Page	275
Ending Page	281
File Size	556409
Page Count	7
File Format	PDF
ISBN	0780326458
DOI	10.1109/IACET.1995.527575
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1995-05-22
Publisher Place	Taiwan
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Job shop scheduling Costs Processor scheduling Petri nets Optimal scheduling Resource management Flexible manufacturing systems Equations Scheduling algorithm Manufacturing systems
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

FMS scheduling using backtracking-free heuristic search based on Petri net state equations

A Heuristic based on Petri Nets modeling for FMS Scheduling problem of makespan minimization

Scheduling FMS with due dates based on Petri net state equations

Scheduling FMS with a Hybrid Heuristic Search Algorithm

FMS scheduling using Petri nets and heuristic search

Heuristic for the resolution of the general FMS cyclic scheduling problem

A Petri nets based object oriented tool for the scheduling of stochastic flexible manufacturing systems

A heuristic algorithm for the periodic scheduling and sequencing job-shop problem

On deadlock-free scheduling in FMS

A heuristic approach based on the state equations of Petri nets for FMS scheduling

Similar Documents

FMS scheduling using backtracking-free heuristic search based on Petri net state equations

A Heuristic based on Petri Nets modeling for FMS Scheduling problem of makespan minimization

Scheduling FMS with due dates based on Petri net state equations

Scheduling FMS with a Hybrid Heuristic Search Algorithm

FMS scheduling using Petri nets and heuristic search

Heuristic for the resolution of the general FMS cyclic scheduling problem

A Petri nets based object oriented tool for the scheduling of stochastic flexible manufacturing systems

A heuristic algorithm for the periodic scheduling and sequencing job-shop problem

On deadlock-free scheduling in FMS

A heuristic approach based on the state equations of Petri nets for FMS scheduling