Article Sidebar

Download
PDF
Statistic
Read Counter : 419 Download : 237

Main Article Content

Abstract

The traditional dimensionality reduction methods can be generally classified into Feature Extraction (FE) and Feature Selection (FS) approaches. The classical FE algorithms are generally classified into linear and nonlinear algorithms. Linear algorithms such as Principal Component Analysis (PCA) aim to project high dimensional data to a lower-dimensional space by linear transformations according to certain criteria. The central idea of PCA is to reduce the dimensionality of the data set consisting of a large number of variables. In this paper, PCA was used to reduce the dimension of flow shop scheduling problems. This mathematical procedure transforms a number of (possibly) correlated jobs into a smaller number of uncorrelated jobs called principal components, which are the linear combinations of the original jobs. These jobs are carefully determined so that from the solution of the reduced problem multiple solutions of the original high dimensional problem can readily be obtained, or completely characterized, without actually listing the optimal solution(s). The results show that by fixing only some critical jobs at the beginnings and ends of the sequence using Johnson's method, the remaining jobs could be arranged in an arbitrary order in the remaining gap without violating the optimality condition that also guarantees minimum completion time. In this regard, Johnson's method was relaxed by terminating the listing of jobs at the first/last available positions when the job with minimum processing time on either machine attains the highest processing time on the other machine for the first time. By terminating Johnson's algorithm at an early stage, the method minimizes the time needed for sequencing those jobs that could be left arbitrarily. By allowing these jobs to be arranged in arbitrary order it gives job sequencing freedom for job operators without affecting minimum completion time. The results of the study were originally obtained for deterministic scheduling problems but they are more relevant on test problems randomly generated from uniform distribution  with lower bound  and upper bound  and normal distribution  with mean  and standard deviation . 

Keywords

Dimension reduction Flow shop scheduling problems Principal component analysis Relaxation of Johnson’s algorithm.

Article Details

References

  1. Johnson, S.M. Optimal two and three-stages production schedules with set up time included, Naval Resh. Logistic Quarterly, 1954, 1(1), 61-68.
  2. Ikram, M. On certain new terms in sequencing theory and on alternative optimal sequences. Pure and Applied Mathematic Sciences, 1975, 2, 1, 45-50.
  3. Prabha. "On alternate optimal solution procedure for solving nx2 flow-shop problem with transportation time and equivalent job-block", Pure and Applied Mathematica Science, 2014, 80, 1-2.
  4. Fora, L., Ikram, M. On Alternative Optimal Sequences for n-Jobs, Three Machines Scheduling Problem with Minimization of Total Elapsed Time, International Journal of Science and Technology, 2016, 6(4), ISSN 2224-3577.
  5. Conway, R.W., Maxwell, W.L., Miller, L. W. Theory of Scheduling, Addison-Wesley, Reading, 1967.
  6. Maggu, Alam and Ikram, M. On certain types of sequencing problems with n-jobs and m-machines, Pure and a Applied Mathematika Science, 1975, 1(2), 55-59.
  7. Ancâu, M. On Solving flow-shop Scheduling Problems, The Publishing House Proceedings of the Romanian Academy, 2012, 13, 71-79.
  8. Palmer, D.S. "Sequencing jobs through a multi-stage process in the minimum total time-a quick method of obtaining a near optimum", Operational Research Quarterly, 1965, 16(1), 101-107.
  9. Gupta, J.N.D. A functional Heuristic Algorithm for flow shop scheduling Problem, Journal of Operational Research Society, 1971, 22(1), 39-47.
  10. Campbell, H.G., Dudek, R. A., Smith, M. L. A heuristic algorithm for the n job, m machine sequencing problem, Management Science, 1970, 16(10), 630-637.
  11. Nawaz, M, Enscore Jr., E., Ham I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, OMEGA, The International Journal of Management Science, 1983, 11(1), 91-95.
  12. Koulamas, C. A new constructive heuristic for the flow-shop scheduling problem, European Journal of Operational Research Society, 1988, 105, 66-71.
  13. Dannenbring, D.G. An evaluation of flow shop sequencing heuristics, Management Science, 1977, 23(11), 1174-1182.
  14. Neppalli, V.R.; Chen, C.L.; Gupta, J.N.D. Genetic algorithms for the two-stage bicriteria flow shop problem. Eur. J. Oper. Res., 1996, 95, 356-373.
  15. Daniels, R.L., Chambers, R.J. Multi-objective flow shop scheduling, Naval Research Logistics (NRL), 1990, 37, 6, 981-995.
  16. Sayin, S., Karabati, S. Theory and methodology a bicriteria approach to the two-machines flow shop scheduling problem, European Journal of Operational Research, 1999, 113(2), doi: 10.1016/S0377-2217(98)00009-5.
  17. Yeh, W.C. A new branch-and-bound approach for the n/2/flowshop/αF+〖β∁〗_max flow shop scheduling problem, Computers and Operations Research, 1999, 26(13), 1293-1310.
  18. Yandra, H. Tamura. new multiobjective genetic algorithm with heterogeneous population for solving flow shop scheduling problems, International Journal of Computer Integrated Manufacturing, 2007, 20(5), 465-477.
  19. Lebbar, G.A., El-Abbassi, Jabri, I.A., El Barkany, A., Darcherif, M. Multi-criteria blocking flow shop scheduling problems: Formulation and performance analysis, Advances in Production Engineering and Management, 2018, 13, 136-146.
  20. Radeleczki, S., T òth, T., G öndri-Nagy, J. A multiple (extended) application of the Johnson’s algorithm for the two-machine manufacturing cell scheduling based on group technology, Production Systems and Information Engineering, Miskolc, 2003, 1, 55-69.
  21. Baker, K.R., Trietsch, D. Principles of sequencing and scheduling, Hoboken: Wiley, 2009.
  22. Han, J., Kamber, M., Pei, J. Data Mining Concepts and Techniques (3ed.), Elsevier, 2012.
  23. Maggu, P.L. and Das, G. "On 2xn sequencing problem with transportation times of Jobs", Pure and' Applied Mathematika Sciences, 1980, 12(1-2), 1-6.
  24. Burges, C.J.C. Dimension Reduction: A Guided Tour, Foundations and Trends in Machine Learning, 2009, 2(4), 275-365.
  25. Indhumathi, R., Sathiyabama, S. Reducing and Clustering high Dimensional Data through Principal Component Analysis, International Journal of Computer Applications, 2010, 11(8), 1-4.
  26. Yan, J., Zhang, B., Liu, N., Yan, S., Cheng, Q., Fan, W., Yang, Q., Xi, W., Chen, Z. Effective and efficient dimensionality reduction for large-scale and streaming data preprocessing. IEEE transactions on knowledge and data engineering, 2006, 18(3), 320-332.