Case Studies
By now, the following case studies are available:
- Manufacturing control proposed by Paul Valckenaers,
- Space conformation of molecules proposed by Pierre Glize.
- Managing Computer Networks Through Self-Organization proposed by Salima Hassas.
A framework is also available to work on these case studies in the private zone.
Manufacturing Control
Proposed by: Paul Valckenaers, K.U.Leuven (B)
The description of this case study is available:
Benchmark System Description
The benchmark comprises the coordination and control of the internal logistics of a manufacturing department. Finished parts have to be delivered against a given due date for assembly in another department. Parts are transported in containers. Typically, a container holds about 10 parts, but this may vary. The system comprises a grid of container storage spaces, distributed across the manufacturing department. The system also comprises 10 workstations with varying properties and capabilities. Workstations have two or three locations at which a container can be placed. An operator picks parts out of one container, processes them in a pipelined fashion on the machines in his/her workstation, and places processed parts in another container at her/his workstation. An automated transporter, moving over rails, normally transports the containers. It can carry maximally two containers at any given time. In addition, carts handled by human operators can also transport parts (without the container), which also is how the parts travel to the assembly department when they are finished. The parts enter the system in a container through the storage system. The systems produces a mix of products, imposing varying loads on the workstations. The transport system has sufficient capacity on average but intermittently experiences rush hour complications. Operators have varying qualifications (having received training in function of shortages that occurred historically). The operator schedule is given.
Perturbations
Machine breakdown, process failures, process time variations, order arrival, rush order arrival, operator unavailability, operator switch (other skills), etc.
Scenario
Data files on order arrival, product mix, product recipe/routing, ... can be made available. Breakdowns... are generated along stochastic distribution including correlated occurrences of disturbances. Operation of the system is described above.
Remark: one simpler and one larger benchmark are being developed as well.
Space Conformation of Molecules
Proposed by Pierre Glize, IRIT (F).
The description of this case study is available:
Search for Drugs
Structural Biology is interested in the relationship between the structure of molecules and their biological function. In a general way, questions more often depend on the field of pharmacology. Thus for a known membrane receiver, finding a ligand, i.e. a complementary medicamentous molecule is problematic. It is the docking problem, i.e. the whole set of mechanisms and interactions that play a part during molecular complexes’ formation.
Simulation study of the docking, rather than experimental one, has a long history and most algorithms are daily used in the academic environment as well as in pharmaceutical laboratories. Molecular docking is the centre of practical applications like proteins engineering, drugs design and screening of molecules potentially relevant. It has thus already contributed to new ligands design for anti-Aids and anti-cancer agents, and for the treatment of the diabetes. To obtain significant progress, we need to develop new methods to facilitate the techniques of docking by improving our capacities to understand and analyze docking interactions and to develop assumptions for which molecules could have better interactions. Knowledge of the process of space conformation of interacting molecules (folding) is essential and is the subject of this case study.
Atomic Interactions
A molecule is an assembly of atoms by covalence connections. In fact, strong connections define quasi-stable interatomic distances (in the region of the Angström) for a particular pair of atoms. Such strong connections are supplemented by strict directional impositions due to weak connections. These weak connections, to have an unspecified effectiveness, can act only at short distances, and as great number.
A molecule’s space conformation results from the interatomic distances defined by the strong connections and from interactions due to weak connections. To simplify, a space conformation consists in minimizing the residual weak energy on the whole molecule, while respecting constraints of strong connections. Emergence theories will have to notify this objective for this case study.
In inter-atomic relations, the fundamental role is held by outer-shell electrons, pertaining to orbital most external of interested atoms. A union between atoms results from modifications touching with the distribution in space of their outer-shell electrons. A covalence connection is a connection due to a bilateral pooling of electrons.
When two atoms approach one another, an attraction between the nucleus of the one and the electrons of the other (and vice versa) appears starting from a certain distance (1 Nano meter approximately). This attraction sensibly increases when distance separating nuclei is about 500 Pico meters. But, starting from this distance, electronic obstruction and repulsion forces between charges of the same sign tend to compensate attraction. A balance is established at a defined distance, characteristic of each atom: it is called Van der Waals’ ray. This value is, for example: 120 pm for hydrogen, 140 pm for oxygen, 285 pm for sulphur. Van der Waals’ forces induce a weak energy (about 1kcal/mol). Thus they are interesting for molecular structures cohesion only if they are numerous and applied between neighbouring atoms.
The energy function for weak connections follows a law as indicated on the following curve. X-coordinate represents interatomic distance (in Angström).
Resolution of Space Conformation by Emergence
Molecule’s space conformation research (to find the minimum of residual energy) is an NP-Complete problem i.e. the solution cannot be found in a polynomial time according to the number of atoms in the molecule.
It is amazing that not only do proteins self-assemble -- fold -- but they do so amazingly quickly: some of them do that as fast as a millionth of a second. While this time is very fast on a person's timescale, it is remarkably long for computers to simulate. In fact, it takes about a day to simulate a nanosecond (1/1,000,000,000 of a second). Unfortunately, proteins fold on the tens of microsecond timescale (10,000 nanoseconds). Thus, it would take 10,000 CPU days to simulate folding -- i.e. it would take 30 CPU years! This temporal relationship between nature and simulation worsens even more as the molecule is longer, because Nature is not constrained by considerations about NP-completeness!! Resolution of this type of problem by emergence must satisfy the following constraints:
- Calculation must be distributed (physically or logically) in such a way that the local algorithm does not have all the information about the molecule.
- Calculation must be emergent i.e. local calculations are unaware about information on the total residual energy of the molecule.
- Ideally (a sensational result!!) you could show (by experimentation or formally) that your algorithm finds a solution in a time limited by a polynomial (depending on the number of atoms).
Information Sources
Standard formats of description of molecules exist. For example, a lot of proteins are described in format PDB. A PDB file includes as many lines as atoms in the described molecule, this number varying from 100 to 10000 atoms per molecule.
| ATOM | 2 | CA | MET | A 1 | -5.725 -8.816 21.543 | 1.00 C |
| ID | Amino-acid | 3D-Coordinates |
This line models carbon atom of methionine (one of the 25 amino acids), it contains its 3D coordinates, its identification number in the molecule, the identification number of the amino acids to which it belongs, etc. Information on ‘usual’ methods of calculation by grid computing can be found on the site of Folding@Home.
- Folding@home Distributed Computing: http://folding.stanford.edu/,
- "Virtual Screening: Illusion or Reality?" by Didier Rognan http://www.eleves.ens.fr/home/deniaud/bioinfo/design.pdf - Le criblage virtuel dans l'ère génomique" by Didier Rognan: http://med-chem.u-strasbg.fr/~didier/vs.pdf,
- The RSCB Protein Data Bank: http://www.rcsb.org/pdb/
GO ON!!!
Managing Computer Networks through Self-Organization
Proposed by Salima Hassas, hassas@bat710.univ-lyon1.fr, Université Claude Bernard-Lyon 1 (F).
The description of this case study is available:
- in a pdf format, file size: 37 Ko.
Benchmark description
The benchmark considers a set of applications (processes) processing on an open network of workstations, while dynamically satisying a set of constraints such as:
- dynamic load balancing of processors;
- minimizing communications costs between highly communicating applications;
- optimal sharing of resources and data between process belonging to a same application;
- mutual exclusion between applications accessing a same set of resources.
The openess of the environment implies that during the processing, new workstations (respectively existing workstations) can join (respectively leave) the network. New applications (respectively existing applications) could also be launched (respectively resume their activity). The network could also be subject to perturbations such like workstations breakdowns for example.
Others aspects
Differents aspects could be considered in this benchmark, dynamic routing of processors, network topology evolution (specificities of the problem with respect to some kind of topologies: simplified problem or a more complex problem, etc), prioritizing some constraints satisfaction (different weights accorded to different constraints), etc.
Scenario
Data files on : network topology, applications caracterization , relations between applications , relations to resources access, etc. can be made available. Breakdowns are generated along stochastic distribution including correlated occurrences of disturbances. Operation of the system is described above.
