S-graph

Last updated
Visual representation of an S-graph S-graph.gif
Visual representation of an S-graph

The S-graph framework is an approach to solving batch process scheduling problems in chemical plants. [1] [2] S-graph is suited for the problems with a non-intermediate storage (NIS) policy, which often appears in chemical productions, but it is also capable of solving problems with an unlimited intermediate storage (UIS) policy. [2]

Batch production

Batch production is a technique used in manufacturing, in which the object in question is created stage by stage over a series of workstations, and different batches of products are made. Together with job production and mass production it is one of the three main production methods.

Chemical plant industrial process plant that manufactures chemicals

A chemical plant is an industrial process plant that manufactures chemicals, usually on a large scale. The general objective of a chemical plant is to create new material wealth via the chemical or biological transformation and or separation of materials. Chemical plants use specialized equipment, units, and technology in the manufacturing process. Other kinds of plants, such as polymer, pharmaceutical, food, and some beverage production facilities, power plants, oil refineries or other refineries, natural gas processing and biochemical plants, water and wastewater treatment, and pollution control equipment use many technologies that have similarities to chemical plant technology such as fluid systems and chemical reactor systems. Some would consider an oil refinery or a pharmaceutical or polymer manufacturer to be effectively a chemical plant.

Contents

Overview

The S-graph representation exploits problem-specific knowledge to develop efficient scheduling algorithms. [2] In the scheduling problem, there are products, and a set of tasks, which have to be performed to produce a product. There are dependencies between the tasks, and every task has a set of needed equipment that can perform the task. Different processing times can be set for the same task in different equipment types. It is possible to have more pieces of equipment of the same type, or define changeover times between two tasks performed on a single piece of equipment.

Algorithm an unambiguous specification of how to solve a class of problems

In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems. Algorithms can perform calculation, data processing, and automated reasoning tasks.

There are two types of the scheduling problems that can be handled:

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics, from evolutionary biology to computer science, etc.

Related Research Articles

Computational complexity theory focuses on classifying computational problems according to their inherent difficulty, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph. Both problems are NP-complete.

Computer science is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. One well known subject classification system for computer science is the ACM Computing Classification System devised by the Association for Computing Machinery.

Directed acyclic graph directed graph with no directed cycles

In mathematics, particularly graph theory, and computer science, a directed acyclic graph, is a finite directed graph with no directed cycles. That is, it consists of finitely many vertices and edges, with each edge directed from one vertex to another, such that there is no way to start at any vertex v and follow a consistently-directed sequence of edges that eventually loops back to v again. Equivalently, a DAG is a directed graph that has a topological ordering, a sequence of the vertices such that every edge is directed from earlier to later in the sequence.

In computing, scheduling is the method by which work specified by some means is assigned to resources that complete the work. The work may be virtual computation elements such as threads, processes or data flows, which are in turn scheduled onto hardware resources such as processors, network links or expansion cards.

In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which can allow more than two choices for the value of each variable. But in contrast to those more general problems, which are NP-complete, 2-satisfiability can be solved in polynomial time.

Belief propagation, also known as sum-product message passing, is a message-passing algorithm for performing inference on graphical models, such as Bayesian networks and Markov random fields. It calculates the marginal distribution for each unobserved node, conditional on any observed nodes. Belief propagation is commonly used in artificial intelligence and information theory and has demonstrated empirical success in numerous applications including low-density parity-check codes, turbo codes, free energy approximation, and satisfiability.

MapReduce is a programming model and an associated implementation for processing and generating big data sets with a parallel, distributed algorithm on a cluster.

Scheduling is the process of arranging, controlling and optimizing work and workloads in a production process or manufacturing process. Scheduling is used to allocate plant and machinery resources, plan human resources, plan production processes and purchase materials.

The Resource-Task Network (RTN) is a unified framework for the description and solution of a variety of process scheduling problems. It was developed by Prof. Costas Pantelides at the Centre for Process Systems Engineering, Imperial College of Science, Technology and Medicine in London, England. The RTN allows the development of simple mathematical programming formulations based on the uniform characterization of all available resources.

The genetic algorithm is an operational research method that may be used to solve scheduling problems in production planning.

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity.

In graph theory and combinatorial optimization, a closure of a directed graph is a set of vertices with no outgoing edges. That is, the graph should have no edges that start within the closure and end outside the closure. The closure problem is the task of finding the maximum-weight or minimum-weight closure in a vertex-weighted directed graph. It may be solved in polynomial time using a reduction to the maximum flow problem. It may be used to model various application problems of choosing an optimal subset of tasks to perform, with dependencies between pairs of tasks, one example being in open pit mining.

Flow shop scheduling problems, are a class of scheduling problems with a workshop or group shop in which the flow control shall enable an appropriate sequencing for each job and for processing on a set of machines or with other resources 1,2,...,m in compliance with given processing orders. Especially the maintaining of a continuous flow of processing tasks is desired with a minimum of idle time and a minimum of waiting time. Flow shop scheduling is a special case of job shop scheduling where there is strict order of all operations to be performed on all jobs. Flow shop scheduling may apply as well to production facilities as to computing designs.

In graph theory a process-graph or P-graph is a directed bipartite graph used in workflow modeling.

Apache Hama

Apache Hama is a distributed computing framework based on bulk synchronous parallel computing techniques for massive scientific computations e.g., matrix, graph and network algorithms. It is a Top Level Project under the Apache Software Foundation. It was created by Edward J. Yoon, who named it and was inspired by Google's Pregel large-scale graph computing framework described in 2010.

In job shop scheduling and graph drawing, the Coffman–Graham algorithm is an algorithm, named after Edward G. Coffman, Jr. and Ronald Graham, for arranging the elements of a partially ordered set into a sequence of levels. The algorithm chooses an arrangement such that an element that comes after another in the order is assigned to a lower level, and such that each level has a number of elements that does not exceed a fixed width bound W. When W = 2, it uses the minimum possible number of distinct levels, and in general it uses at most 2 − 2/W times as many levels as necessary.

Apache Spark open-source data analytics cluster computing framework

Apache Spark is an open-source distributed general-purpose cluster-computing framework. Originally developed at the University of California, Berkeley's AMPLab, the Spark codebase was later donated to the Apache Software Foundation, which has maintained it since. Spark provides an interface for programming entire clusters with implicit data parallelism and fault tolerance.

Process network synthesis (PNS) is a method to represent a process structure in a 'directed bipartite graph'. Process network synthesis uses the P-graph method to create a process structure. The scientific aim of this method is to find optimum structures.


Most of the terms listed in Wikipedia glossaries are already defined and explained within Wikipedia itself. However, glossaries like this one are useful for looking up, comparing and reviewing large numbers of terms together. You can help enhance this page by adding new terms or writing definitions for existing ones.

References

  1. Holczinger, T.; J Romero; L Puigjaner; F Friedler (2002-12-02). "Scheduling of Multipurpose Batch Processes with Multiple Batches of the Products". Hungarian Journal for Industrial Chemistry. 30: 305–312.
  2. 1 2 3 Romero, Javier; Luis Puigjaner; Tibor Holczinger; Ferenc Friedler (2004-02-18). "Scheduling intermediate storage multipurpose batch plants using the S-graph". American Institute of Chemical Engineers . 50 (2): 403–417.