SAS algorithm

Monte Carlo/simulated annealing (MC/SA) algorithm for sequential assignment in uniformly 13C, 15N-labeled proteins [137]. The two-dimensional (2D) NCACX and NCOCX spectra measured for the fibril samples of full-length Syrian hamster prion protein (residues 23-231) have been analyzed by the MC/SA protocol, from which it has been concluded that the fibril core is formed primarily in the region of residues 173-224 [54]. 

To apply these ideas to a general optimization problem, let the system state vector q correspond to the objects to be optimized (job sequences, vehicle routes, or vectors of decision variables), denoted by x. The system energy level corresponds to the objective function fix). As in Section 10.5.1, let N(x) denote a neighborhood of x. The following procedure (Floquet et al., 1994) specifies a basic SA algorithm ... 

Viewing the SA algorithm in terms of Markov chains, Greene and Supowit [8] pointed out that any type of function may be used for the decision making process about acceptance of new configurations, provided the detailed balance equation for the Markov process is satisfied. 

We chose the above problem merely to evaluate the potential of SA for the batch process scheduling problems. It was an obvious choice, because it has been studied extensively (Ku et al. 1987) in the literature, thus algorithms for comparison already exist in the literature. This problem of finding a sequence with minimum total time (called makespan) to produce all N batches has been shown to be NP-complete for M>2 by Garey et al. (1976), thus no polynomialtime algorithms exist for getting optimal solutions. We now describe our implementation of the SA algorithm. 

Clearly, our version of the SA algorithm is not optimum. Das et al. (1989) and Malone (1989) have studied this problem further to optimize the SA procedure. Even this fairly crude version of SA was quite successful as compared to some heuristic algorithms that we discuss below. 

To demonstrate the applicability of the improved SA algorithm, as discussed above, let us now apply it to a fairly large scheduling problem for the plant in Figure 2. The data for the example are summarized in Table 4. Figures 9-11 show the results of the computation. The algorithm was coded in C language and the CPU times are on a SUN SPARCStation 10. 

It is difficult to say if the schedule in Figure 11 is optimal. However, it is the best available at present, as we could not improve it by manually changing the processing orders on the basis of experience. When the same problem was solved without the modification to SA, the computation time was four times as long. This clearly indicates the impact of a small modification in the SA algorithm. 

Several variants of the basic SA algorithm have been developed, which differ in the choice of the CF, in the design of the annealing schedule or in the procedure for the generation of the trial configurations. For example, Andreev et al. reduce T at a preset rate and, for each T, perform several moves which increase as the acceptance ratio decreases David et introduced the following relevant novelties, included in the computer program DASH ... 

Discontinuities pose major numerical problems if the SA algorithm requires a smooth model. 

In theory, independent input parameters are required for performing variance-based SA. It is not clear what happens with the SA algorithms in the presence of dependencies between the inpnt parameters or to what extent the results can be interpreted. 

Fig. 3 Left Superimpositions of the structures of trypsin ligand 1 (black wire) and ligand 7 (grey stick) obtained using the MC/SA algorithm with various descriptors smoothed at t varying between 1.7 and 1.4 bohr. Isocontours of the PASA ED, CD Coulomb potential,...

---