ORIGINAL_ARTICLE
Modern Computational Applications of Dynamic Programming
Computational dynamic programming, while of some use for situations typically encountered in industrial and systems engineering, has proved to be of much greater significance in many areas of computer science. We review some of these applications here.
https://www.jise.ir/article_4027_4987424e2245cecf6c971d9eb641deef.pdf
2010-11-01
152
155
Dynamic programming applications
Stuart
Dreyfus
1
Department of Industrial Engineering and Operations Research, University of California at Berkeley, CA 94720, USA
AUTHOR
[1] Smithline L.M. (2009); American Scientist 97(2); 142-147.
1
[2] Dreyfus S., http://www.lionhrtpub.com/orms/orms-4-10/forum.html, 2010.
2
[3] Wikipedia, http://en.wikipedia.org/wiki/Sequence_alignment, 2010a.
3
[4] Wikipedia, http://en.wikipedia.org/wiki/Hidden_Markov_model, 2010b.
4
[5] Wikipedia, http://en.wikipedia.org/wiki/Dynamic_programming, 2010c.
5
[6] Wikipedia, http://en.wikipedia.org/wiki/Temporal_difference_learning, 2010d.
6
ORIGINAL_ARTICLE
A Set of Algorithms for Solving the Generalized Tardiness Flowshop Problems
This paper considers the problem of scheduling n jobs in the generalized tardiness flow shop problem with m machines. Seven algorithms are developed for finding a schedule with minimum total tardiness of jobs in the generalized flow shop problem. Two simple rules, the shortest processing time (SPT), and the earliest due date (EDD) sequencing rules, are modified and employed as the core of sequencing determination for developing these seven algorithms. We then evaluated the effectiveness of the modified rules through an extensive computational experiment.
https://www.jise.ir/article_4029_221a99a8828aafb50b121de62f29ab9b.pdf
2010-11-01
156
166
Flowshop
Total tardiness
Intermediate due dates
Farhad
Ghassemi-Tari
1
Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran
AUTHOR
Laya
Olfat
2
School of Management, Alameh-Tabatabie University, Tehran, Iran
AUTHOR
[1] Baker K.R. (1974), Introduction to Sequencing and Scheduling; John Wiley & Sons, Inc.; New York,
1
ISBN 0-471-04555-1.
2
[2] Bilge U., Kirac F., Kurtulan M., Pekgun P. (2004), A tabu search algorithm for parallel machine total
3
tardiness problem; Computers & Operations Research 31(3); 397-414.
4
[3] Bulbul k., Kaminsky P., Yano C. (2004), Flow Shop scheduling with earliness, tardiness, and
5
intermediate inventory holding cost; Naval Logistics 51; 407-445.
6
[4] Carroll D.C. (1965), Heuristic sequencing of jobs with single & multiple components; Ph.D.
7
dissertation, Sloan School of Management; Massachusetts Institute of Technology, Mass.
8
[5] Chio S.W., Lee G.C., Kim Y.D. (2005), Minimizing total tardiness of orders with reentrant lots in a
9
hybrid flow shop; International Journal of Production Research 43(11); 2149-2167.
10
[6] Ghessemi-Tari F., Olfat L. (2004), Two COVERT based algorithms for solving the generalized flow
11
shop problems; Proceeding of the 34th International Conference on Computers and Industrial
12
Engineering; 29-37.
13
[7] Ghessemi-Tari F., Olfat L. (2007), Development of a set of algorithms for the multi-projects
14
scheduling problems; Journal of Industrial and Systems Engineering 1(1); 11-17.
15
[8] Gupta N.D., Kruger K., Lauff V., Werner F., Sotskov Y.N. (2002), Heuristics for hybrid flow shops
16
with controllable processing times and assignable due dates; Computers & Operations Research
17
29(10); 1417-1439.
18
[9] Lauff V., Werner F. (2004), On the complexity and some properties of multi-stage scheduling
19
problems with earliness and tardiness penalties; Computers & Operations Research 31(3); 317-345.
20
[10] Lee G.C., Kim Y.D. (2004), A branch and bound for a two stage hybrid flow shop scheduling problem
21
minimizing total tardiness; International Journal of Production Research 42(22); 4731-4743.
22
[11] Lin H.T., Liao C.J. (2003), A case study in a two-stage hybrid flow shop with setup time and dedicated
23
machines; International Journal of Production Economics 86(2); 133-143.
24
[12] Takaku K., Yura K. (2005), Online scheduling aiming to satisfy due date for flexible flow shops;
25
JSME International Journal Series C 48(1); 21-25.
26
[13] Yeh W., Allahverdi A. (2004), A branch and Bound algorithm for the three machine flow shop
27
scheduling problem with bi-criteria of make-span and total flow time; International Transaction in
28
Operations Research 11(30); 323-327.
29
ORIGINAL_ARTICLE
A Genetic Based Scheduling Algorithm for the PHSP with Unequal Batch Size Inbound Trailers
This paper considers the parcel hub scheduling problem (PHSP) with unequal batch size inbound trailers, which is a combinatorial optimization problem commonly found in a parcel consolidation terminal in the parcel delivery industry (PDI). The problem consists of processing a large number of inbound trailers at a much smaller number of unload docks. The parcels in the inbound trailers must be unloaded, sorted and transferred to the load docks, and loaded onto the outbound trailers. Because the transfer operation is labor intensive and the PDI operates in a time-sensitive environment, the unloading, sorting, transferring, and loading of the parcels must be done in such a way as to minimize the timespan of the transfer operation. A genetic algorithm is used to solve the PHSP. An experimental analysis shows that the algorithm is able to produce solution results that are within 17% of the lower bound, 16% better than a competing heuristic, and 24% better than random scheduling.
https://www.jise.ir/article_4030_b9f14d64f99016cc7e7dd7a0248c15dd.pdf
2010-11-01
167
182
Distribution
Cross dock
Sortation
Genetic algorithm
Work load balancing received
Douglas L.
McWilliams
1
Mississippi State University-Meridian, 1000 Highway 19 North, Meridian, MS 39307-5799
AUTHOR
[1] Bartholdi J., Gue K. (2000), Reducing Labor Costs in an LTL Crossdocking Terminal; Operations Research 48(6); 823-832.
1
[2] Basset M., Pekny J., Reklaitis G. (1995), Decomposition Techniques for the Solution of Large-Scale Scheduling Problems; American Institute of Chemical Engineering Journal 42(12); 3373.
2
[3] Felix Ammah-Tagoe (2006), Freight in America: A New National Picture; Research and Innovative Technology Administration, Bureau of Transportation Statistics; Washington, DC.
3
[4] Gilbert D. (1934), Parcel Conveyors; Post Office Electrical Engineers’ Journal 27(3); 179-186.
4
[5] Goodison H. (1981), Parcel Sorting Systems and Ancillary Postal Equipment; Post Office Electrical Engineers’ Journal 74(3); 271-277.
5
[6] Goldberg D. (1989), Genetic algorithms in search, optimization, and machine learning; Addison-Wesley: Reading; MA.
6
[7] Gould L. (1991), Increase Productivity by Choosing the Right Sortation Conveyor; Modern Materials Handling 46(7); 54-56.
7
[8] Graham R.L. (1969), Bounds on Multiprocessing Timing Anomalies; SIAM Journal of Applied Mathematics 17(2); 416–429.
8
[9] Gue K. (1996), Freight Terminal Layout and Operations; Doctoral dissertation, Georgia Institute of Technology, 1995; (Dissertation Abstract International, B56/11, 6322-6432).
9
[10] Haupt R., Haupt S. (1998), Practical Genetic Algorithms; New York: John Wiley & Sons.
10
[11] Khmelnitsky E., Kogan K., Maimon O. (2000), A Time-Decomposition Method for Sequence-Dependent Setup Scheduling under Pressing Demand Conditions; IEEE Transactions on Analytical Control 45(4); 638-652.
11
[12] Lai J. (2007), Surrogate search: A Simulation Optimization Methodology for Large-Scale Systems; Doctoral dissertation, University of Pittsburgh, 2006; (Dissertation Abstracts International, B67/08, 205-364).
12
[13] Masel D., Goldsmith D. (1997), Using a Simulation Model to Evaluate the Configuration of a Sortation Facility; Proceedings of the 29th Winter Simulation Conference; Atlanta, GA: IEEE Computer Society, 1210-1213.
13
[14] Masel D. (1998), Adapting the Longest Processing Time Heuristic (LPT) for Output Station Assignment in a Sortation Facility; Proceedings of the 7th Industrial Engineering Research Conference, Phoenix, Arizona: IIE.
14
[15] McWilliams D. (2009), Genetic-Based Scheduling to Solve the Parcel Hub Scheduling Problem; Computers and Industrial Engineering 56(4); 1607-1616.
15
[16] McWilliams D., Stanfield M., Geiger C. (2008), Minimizing the Completion Time of the Transfer Operations in a Central Parcel Consolidation Terminal with Unequal-Batch-Size Inbound Trailers; Computers and Industrial Engineering 54(4); 709-720.
16
[17] McWilliams D., Stanfield M., Geiger C. (2005), The Parcel Hub Scheduling Problem: A Simulation-Based Solution Approach; Computers and Industrial Engineering 49(3); 393-412.
17
[18] Rohrer M. (1995), Simulation and Cross Docking; Proceedings of the 1995 Winter Simulation Conference; IEEE Computer Society, 846-849.
18
ORIGINAL_ARTICLE
Learning Curve Consideration in Makespan Computation Using Artificial Neural Network Approach
This paper presents an alternative method using artificial neural network (ANN) to develop a scheduling scheme which is used to determine the makespan or cycle time of a group of jobs going through a series of stages or workstations. The common conventional method uses mathematical programming techniques and presented in Gantt charts forms. The contribution of this paper is in three fold. Firstly, the learning curve which is characterized by a coefficient is considered in the computation work. Secondly, this work is limited to small number of jobs and is useful for project based pilot runs which involve learning. Lastly, the scheduling scheme is developed in ANN as an alternate method. Extensive and successful training using the input and output vector pairs were done to establish the proposed method. Comparison was done for the tested outputs and results produced seem reliable.
https://www.jise.ir/article_4031_bf5b6ad8bf3cbc51385baf2acc84fcde.pdf
2010-11-01
183
192
Learning curve
scheduling
Back Propagation Network
Gantt chart
Suresh
Kumar
1
Department of Electrical and Electronics Engineering Technology, Yanbu Industrial College, Yanbu Al Sinaiyah, Kingdom of Saudi Arabia
AUTHOR
A.
Arunagiri
2
Department of Electrical and Electronics Engineering Technology, Yanbu Industrial College, Yanbu Al Sinaiyah, Kingdom of Saudi Arabia
AUTHOR
[1] Argote L., Epple D. (1990), Learning curves in manufacturing; Science 247(4945); 920-924.
1
[2] Bohlen G.A., Barany J.W. (1976), A learning curve prediction model for operators performing industrial bench assembly operations; International Journal of Production Research 14(2); 295-303.
2
[3] Guo Z.X., Wong W.K, Leung S.Y.S, Fan F.T (2009), Intelligent production control decision support system for flexible assembly lines; Expert Systems with Applications: An International Journal 36(8); 4268- 4277.
3
[4] Kumar S., Omar M.K. (2005a), Stochastic re-entrant line modeling for an environmental stress testing in a semiconductor assembly industry; Applied Mathematics and Computation 173(1); 603-615.
4
[5] Kumar S., Omar M.K. (2005b), Performance measure in a probabilistic reflow screening line using mean value analysis; AIUB Journal of Science and Engineering 4(1); 53-58.
5
[6] Kumar S. (2007), Performance analysis of a probabilistic re-entrant line in an environmental stress testing operation; Doctoral Thesis; Multimedia University, Malaysia.
6
[7] Kumar S. (2008), Modeling of a probabilistic re-entrant line bounded by limited operation utilization time; Journal of Industrial and Systems Engineering 2(1); 28-40.
7
[8] McCollum P. (1997), An introduction to back-propagation neural networks; The Newsletter of the Seattle Robotics Society; November.
8
[9] Moghaddam R.T., Kanani Y.G., Cheraghalizadeh R. (2008), A genetic algorithm and memetic algorithm to sequencing and scheduling of cellular manufacturing systems; International Journal of Management Science and Engineering Management 3(2); 119-130.
9
[10] Shihab K. (2006), A back propagation neural network for computer network security; Journal of Computer Science 2(9); 1549-3636.
10
[11] Stafford E.F., Tseng F.T. (2002), Two models for a family of flowshop sequencing Problems; European Journal of Operational Research 142; 282-293.
11
[12] Stevenson W.J. (2006), Operations Management; 9th ed. McGraw-Hill; New York, 349-357.
12
ORIGINAL_ARTICLE
A Mushy State Simulated Annealing
It is a long time that the Simulated Annealing (SA) procedure is introduced as a model-free optimization for solving NP-hard problems. Improvements from the standard SA in the recent decade mostly concentrate on combining its original algorithm with some heuristic methods. These modifications are rarely happened to the initial condition selection methods from which the annealing schedules starts or the time schedule itself. There are several parameters in the process of annealing, the adjustment of which affects the overall performance. This paper focuses on the importance of initial temperature and then proposes a lower temperature with low energy to speed up the process, using an auxiliary memory to buffer the best solution. Such an annealing indeed starts from a “mushy state” rather than a quite liquid molten material. The mushy state characteristics depends on the problems that SA is being applied to solve for. In this paper, the Mushy State Simulated Annealing (MSSA) is fully developed and then applied to the popular Traveling Salesman Problem (TSP). The mushy state may be obtained by some simple methods like crossover elimination. A very fast version of a Wise Traveling Salesman, who starts from a randomly chosen city and seeks for the nearest one as the next, is also applied to initiate SA by a low-energy, low-temperature state. This fast method results in quite accurate solutions compared to the methods recently cited in the literature.
https://www.jise.ir/article_4032_38c7411d1c4c900db3e1e74ab7f47e4b.pdf
2010-11-01
193
208
Combinatorial Optimization
Traveling Salesman
Initial Condition
Kambiz
Shojaee
1
Low-Power High-Performance Nanosystems Laboratory, School of Electrical and Computer Engineering, University of Tehran
AUTHOR
Hamed
Shakouri
2
Industrial Engineering Department, University of Tehran, Tehran, Iran
AUTHOR
Mohammad Bagher
Menhaj
3
Electrical Engineering Department, Amirkabir University of Technology
AUTHOR
[1] Aarts E., Korst J. (1989), Simulated Annealing and Boltzmann Machines: A Stochastic Approach to
1
Combinatorial Optimization and Neural Computing; Wiley, New York.
2
[2] Aras N., Altınel I.K., Oommen J. (2003), A Kohonen-Like Decomposition Method For The Euclidean
3
Traveling Salesman Problem Knies-Decompose; IEEE Transactions on Neural Network 14(4).
4
[3] Chen H., Flann S.N., Watson W.D. (1998), Parallel Genetic Simulated Annealing: A Massively
5
Parallel SIMD Algorithm; IEEE Transactions on Parallel and Distributed Systems 9(2); 126-136.
6
[4] Cheng C.-H., Lee W.-K., Wong K.-F. (2002), A Genetic Algorithm-Based Clustering Approach for
7
Database Partitioning; IEEE Transactions on Systems, Man, and Cybernetics—PART C: Applications
8
and Reviews 32(3).
9
[5] Cho H.J., Young Oh S., Choi D.-H. (1998), Population-oriented simulated annealing technique based
10
on local Temperature concept; Electronics Letters 34(3); 312-313.
11
[6] Creput J.C., Koukam A. (2008), A memetic neural network for the Euclidean traveling salesman
12
problem; Neurocomputing.
13
[7] Dueck G., Scheuer T. (1990), Threshold accepting: A general purpose optimization algorithm
14
appearing superior to simulated annealing; J. Computer. Phys. 90; 161–175.
15
[8] Garey M.R., Johnson D.S. (1979), Computers and Intractability: A Guide to the Theory of NPCompleteness;
16
Freeman, New York.
17
[9] He Y. (2002), Chaotic Simulated Annealing With Decaying Chaotic Noise; IEEE Transactions on
18
Neural Networks 13(6); 1526-1531.
19
[10] Hung M.-H., Shu L.-S., Ho S.-J., Hwang S.-F., Ho S.-Y. (2008); A Novel Intelligent Multiobjective
20
Simulated Annealing Algorithm for Designing Robust PID Controllers; Proceeding of IEEE
21
Transactions on Systems, Man, and Cybernetics—PART A: Systems and Humans 38(2); 319-330.
22
[11] Ingber L., Rosen B. (1992), Genetic Algorithms and Very Fast Simulated Reannealing: A Comparison;
23
Mathematical Computer Modeling 16(11); 87-100.
24
[12] Jang J., Sun C., Mizutani E. (1997), Neuro-Fuzzy and Soft Computing; Proc. of the Prentice Hall.
25
[13] Jin H.-D., Leung K.-S., Wong M.-L., Xu Z.-B. (2003), An Efficient Self-Organizing Map Designed by
26
Genetic Algorithms for the Traveling Salesman Problem; IEEE Transactions on Systems, Man, and
27
Cybernetics—PART B: Cybernetics 33(6); 877-888.
28
[14] Kirkpatrick S., Gelatt C.D., Vecchi M.P. (1983), Optimization by simulated annealing; Science 220;
29
671–680.
30
[15] Kravitz S.A., Rutenbar R.A. (1987), Placement by simulated annealing on a multiprocessor; IEEE
31
Trans. Computer-Aided Design Integr. Circuits Syst. 6(4); 534–549.
32
[16] Leung K.-S., Jin H.-D., Xu Z.-B. (2004), An expanding Self-Organizing neural network for the
33
traveling salesman problem; Neurocomputing 62; 267-292.
34
[17] Lin F.-T., Kao C.-Y., Hsu C.-C. (1993), Applying the Genetic Approach to Simulated Annealing in
35
Solving Some NP-Hard Problems; IEEE Transactions on Systems, Man, and Cybernetics, 23(6).
36
[18] Pao D.C.W., Lam S.P., Fong A.S. (1999), Parallel implementation of simulated annealing using
37
transaction processing; IEE Proc-Comput. Digit. Tech.. 146(2); 107-113.
38
[19] Pepper W.J., Golden L.B., Wasil A.E. (2002), Solving the Traveling Salesman Problem With
39
Annealing-Based Heuristics: A Computational Study; IEEE Transactions on Systems, Man, and
40
Cybernetics—PART A: Systems and Humans 32(1).
41
[20] Saadatmand-Tarzjan M., Khademi M., Akbarzadeh M.R.., Abrishami Moghaddam H. (2007), A Novel
42
Constructive-Optimizer Neural Network for the Traveling Salesman Problem; IEEE Transactions on
43
Systems, Man, and Cybernetics—PART B: Cybernetics 37(4).
44
[21] Shakouri G.H., Shojaee K., Behnam T.M. (2009), The Wise Experiencing Traveling Salesman
45
(WETS): Introduction to a simple evolutionary solution for the problem; Proc. in CEC 2009 IEEE
46
Congress on Evolutionary Computation; 18-21 May, Trondheim, Norway; 771-776.
47
[22] Smith K.I., Everson M.R., Fieldsend E.J, Murphy C., Misra R. (2008), Dominance-Based
48
Multiobjective Simulated Annealing; IEEE Transactions on Evolutionary Computation 12(3); 323-
49
[23] Soh A. (1995), Parallel N-ary Speculative Computation of Simulated Annealing; IEEE Transactions
50
on Parallel and Distributed Systems 6(10); 997-1005.
51
[24] Thompson R.D., Bilbro L.G. (2005), Sample-Sort Simulated Annealing; IEEE Transactions on
52
Systems, Man, and Cybernetics—PART B: Cybernetics 35(3); 625-632.
53
[25] Tsang H.H., Wiese K.C. (2007), The Significance of Thermodynamic Models in the Accuracy
54
Improvement of RNA Secondary Structure Prediction Using Permutation-based Simulated Annealing;
55
Proceeding of IEEE Congress on Evolutionary Computation.
56
[26] Wang L., Li S., Tian F., Fu X. (2004), A Noisy Chaotic Neural Network for Solving Combinatorial
57
Optimization Problems: Stochastic Chaotic Simulated Annealing; Transactions on Systems, Man, and
58
Cybernetics—PART B: Cybernetics 34(5); 2119-2125.
59
[27] Wong K.L., Constantinides A.G. (1998), Speculative parallel simulated annealing with acceptance
60
prediction; Electronics Letters 34(3); 312-313.
61
[28] Wu S., Chow W.S.T. (2007), Self-Organizing and Self-Evolving Neurons: A New Neural Network for
62
Optimization; IEEE Transactions on Neural Network 18(2); 385-396.
63
[29] Yip C.P., Pao Y.-H. (1995), Combinatorial Optimization with Use of Guided Evolutionary Simulated
64
Annealing; IEEE Transactions on Neural Networks 6(2); 290-295.
65
[30] Reinelt G. (1995), Tsplib95, http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95,
66