Job shop problem

An alternative model for the job shop problem can be represented by a disjunctive graph. This model is constructed by Roy and Sussmann [10] and extracted here from Pinedo [8]. The job shop structure is modeled by a directed graph G with a set of N nodes and two sets of arcs A and B. Each operation (i, j) of job j on machine k is represented by a node in the graph. The A arcs, called conjunctive (solid), represent the routes of the jobs. If arc i, j) - (k, j) is part of A, then job j has to be processed on machine i before proceeding to machine k, i.e., operation (i, j) precedes operation (fe, j). Two operations that belong to two different jobs and that have to be processed on the same machine are connected to one another by... 

Job-shop problems machines are arranged in a job-shop layout and each job has its own route among machines. 

The most common used notation for theoretical scheduling is the so-called three-field notation introduced by Graham et al. (1979). The notation foresees three fields called a p y. The first field defines the scheduling environment a equal to F stands for flow shop, / for job shop, P for parallel machines, and O for open shop. A number can be inserted to indicate the number of machines. The second field specifies job characteristics indicating, for example, the preemption, ready times, and additional resources. The third field specifies the performance index (objective). Some examples can be the following l Sjk C,nax denotes a single-machine problem with sequence-dependent setup times and minimization of maximum completion time makespan)-, JmWCmax denotes a job-shop problem with m machines an[Pg.1094]

Assignment of each operation to one of its alternative routes (machines) so as to convert the multiple routing job shop problem to a fixed route job shop problem. 

Determination of optimal or near optimal schedules for the flexible job shop problem by assigning the operations to one of its alternative machines and sequencing the operations on the machines for the objective of minimization of makespan time, given the processing time of operations on all its alternative routes and the precedence relationship between the operations". 

The different modules of the p>rop)osed ACO for the flexible job shop problem are outlined as flowchart in Figure 1. The different modules are described below. 

Ho, N.B. Tay, J.C. (2004). GENACE An Efficient Cultural Algorithm for Solving the Flexible Job-Shop Problem. Proceedings of the IEEE Congress on Evolutionary Computation, Vol.l, pp.1759-1766, IEEE. 

J. CARLIER and E. PINSON. An algorithm for solving the job-shop problem. Management science vol.35, no2 February 1989. 

Electroplating is done both in job shops, where a customer s work is plated, and in captive (in-house) shops. There were reported to be about 7500 plating plants in the United States (4) in 1992. This is a decrease from the ca 12,000 reported by the same source in 1980. The reduction, particularly in the number of smaller job shops, is related to the problems in meeting the waste regulations imposed on plating shop effluents. 

To understand the mathematics, consider a large empty space into which a number of production units are to be placed, and assume that the major variable to be optimized is the cost of transporting materials between them. If the manufacturing process is essentially a flow-line operation, then the order in which units should be placed is clear (from the point of view of transport costs), and the problem is simply to fit them into the space available. In a job-shop, where materials are flowing between many or all the production units, the decision is more difficult. All the potential combinations of units and locations... 

These combinatorial problems, and many others as well, have a finite number of feasible solutions, a number that increases rapidly with problem size. In a job-shop scheduling problem, the size is measured by the number of jobs. In a traveling salesman problem, it is measured by the number of arcs or nodes in the graph. For a particular problem type and size, each distinct set of problem data defines an instance of the problem. In a traveling salesman problem, the data are the travel times between cities. In a job sequencing problem the data are the processing and set-up times, the due dates, and the penalty costs. 

As mentioned above, Cho and Wysk (1993) utilized the multilayer perceptron to take the place of the knowledge-based system in selecting candidate scheduling rules. In their proposed framework, the neural network will output a goodness index for each rule based on the system attributes and a performance measure. Sim et al. (1994) used an expert neural network for the job shop scheduling problem. In their approach, an expert system will activate one of 16 subnetworks based on whether the attribute corresponding to the node (scheduling rules, arrival rate factor, and criterion) is applicable to the job under consideration. Then the job with the smallest output value wiU be selected to process. 

A number of approaches have been utihzed in the application of genetic eilgorithms (GA) to job shop scheduling problems (Davis 1985 Goldberg and Lingle 1985 Starkweather et til. 1992) ... 

Heuristic genetic algorithms have been applied to job shop scheduling. In these genetic schemes, problem specific heuristics are incorporated in the recombination operators (such as optimization operators based). 

Foo, Y. S., and Takefuji, Y. (1988a), Stochastic Neural Networks for Solving Job-Shop Scheduling. Part 1 problem representation, in IEEE International Joint Conference on Neural Networks, Vol. 2, pp. 275-282. 

Zhang, C., Yan, R, and Chang, T. (1991), Solving Job-Shop Scheduling Problem with Priority Using Neural Network, in IEEE International Joint Cor erence on Neural Networks, pp. 1361-1366. 

The job shop has a more general structure than the flow shop in which each job go through multiple processing stages (or machines) in an order that might be different than other jobs. The basic job shop scheduling problem holds the same assumptions that were made for the basic flow shop problem. In addition it is assumed that each job may be processed by a machine at most once, i.e., without recirculation. 

---