Journal of Korean Institute of Industrial Engineers (대한산업공학회지)

Korean Institute of Industrial Engineers (대한산업공학회)
권호 표지
DOI QR코드

DOI QR Code

Advanced Distributed Arrival Time Control for Single Machine Problem in Dynamic Scheduling Environment

동적 스케줄링을 위한 분산 도착시간 제어 (Distributed Arrival Time Control) 알고리즘의 개량

  • Ko, Jea-Ho (Department of Industrial Engineering, Hongik University) ;
  • Ok, Chang-Soo (Department of Industrial Engineering, Hongik University)
  • 고재호 (홍익대학교 산업공학과) ;
  • 옥창수 (홍익대학교 산업공학과)
  • Received : 2011.08.18
  • Accepted : 2012.02.04
  • Published : 2012.03.01
Download PDF
⟨ Previous Next ⟩

Abstract

Distributed arrival time control (DATC) is a distributed feedback control algorithm for real-time scheduling problems in dynamic operational environment. Even though DATC has provided excellent performance for dynamic scheduling problems, it can be improved by considering the following considerations. First, the original DATC heavily depends on the quality of initial solution. In this paper, well-known dispatching rules are incorporated DATC algorithm to enhance its performance. Second, DATC improves its solution with adjusting virtual arrival times of jobs to be scheduled in proportion to the gap between completion time and due date iteratively. Since this approach assigns the same weight to all gaps generated with iterations, it fails to utilize significantly more the latest information (gap) than the previous ones. To overcome this issue we consider exponential smoothing which enable to assign different weight to different gaps. Using these two consideration This paper proposes A-DATC (Advanced-DATC). We demonstrate the effectiveness of the proposed scheduling algorithm through computational results.

Keywords

References

  1. Aarts, E. H. L., Frans, M. J., and Habers, E. H. A. (1986), Parallel implementations of the statistical cooling algorithm, VLSI Journal, 4(3), 209-238. https://doi.org/10.1016/0167-9260(86)90002-7
  2. Abdul-Razaq, T. S. and Potts, C. N. (1988), Dynamic programming state-space relaxation for single-machine scheduling, Journal of Operational Research Society, 39(2), 141-152. https://doi.org/10.1057/jors.1988.26
  3. Bagchi, U., Sullivan, R. S., and Chang, Y. L. (1987), Minimising mean squared deviation of completion times about a common due date, Management Science, 33, 894-906. https://doi.org/10.1287/mnsc.33.7.894
  4. Baker, K. R. (1974), Introduction to Sequencing and Scheduling, Wiley, New York.
  5. Cho, S.-H. and Erkoc, M. (2009), Design of predictable production scheduling model using control theoretic approach, international, Journal of Production Research, 47(11), 2976-2993.
  6. Glover, F. (1986), Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, 13(5), 533-549. https://doi.org/10.1016/0305-0548(86)90048-1
  7. Goldberg, D. E. (1989), Genetic algorithms in search, optimisation, and machine learning, Addison-Wesley, Boston.
  8. Holt, C. C. (1957), Forecasting Seasonal and Trends by Exponentially Weighted Moving Averages, Carnegie Institute of Technology, Pittsburgh.
  9. Kim, J.-D. and Ok, C.-S. (2008), Distributed feedback control algorithm for dynamic truck loading scheduling problem, Applied Mathematics and Computation, 1, 275-284.
  10. Lee, S.-H. and Lee, S.-W. (2009), Ant colony system for vehicle routing problem with simultaneous delivery and pick-up under time windows, Journal of the Korean Institute of Industrial Engineers, 35(2), 160-170.
  11. Li, G. (1997), Single machine earliness and tardiness scheduling, European Journal of Operational Research, 96, 546-558. https://doi.org/10.1016/S0377-2217(96)00062-8
  12. Parunak, H. D. (1991), Characterising the manufacturing scheduling problem, Journal of Manufacturing Systems, 10(3), 241-259. https://doi.org/10.1016/0278-6125(91)90037-3
  13. Prabhu, V. V. and Duffie, N. A. (1999), Nonlinear dynamics in distributed arrival time control of heterarchical manufacturing systems, IEEE Transactions on Control Systems Technology, 1(6), 724-730.
  14. Prabhu, V. V. (2000), Performance of Real-time Distributed Arrival Time Control in Heterarchical Manufacturing Systems, IIE Transactions, 32, 323-331.
  15. Pirlot, M. (1992), General local search heuristics in combinatorial optimisation : a tutorial, Belgium Journal of Operations Research, 32, 8-67.
  16. Sabuncuoglu, I. and Karabuk, S. (1999), Rescheduling frequency in an FMS with uncertain processing times and unreliable machines, Journal of Manufacturing Systems, 18(4), 269-283.
  17. Simchi-Levi, D. (2006), Designing and Managing the Supply Chain, 3, McGraw-Hill, New York.