A Heuristic Algorithm to Minimize Mean Squared Deviation of Completion Times
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
This paper addresses the problem of minimizing the mean squared deviation(MSD) of completion times from a common due date in unconstrained case. The unconstrained MSD is known to be NP-complete and a heuristic algorithm which consists of two phases(schedule construction and improvement) is proposed. In the schedule construction phase, by using the simulated annealing technique and balanced V-shape schedule, good initial solutions are constructed. Then, the improvement phase enhances the quality of solution based on the concepts of both better dual and better pair. The developed two phases are serially employed to obtain the schedule of minimizing MSD problem. The first phase focuses on the finding of good initial solution and the second phase stresses on the improvement of solution quality. For the unconstrained MSD problem, the best known heuristic the algorithm is in Ventura and Weng(1995) and the algorithm in Gupta et al.(1990) finds fairly good solutions with much less computational time than one in Ventura and Weng(1995). The proposed heuristic finds all optimal solutions of the test problems in Eilon and Chowdhury(1977) and Gupta et al.(1990) with much less computational time compared with the heuristic in Ventura and Weng(1995). In order to show the performance of proposed heuristic in detail when job sizes are large, several test problems are generated. The computational results show that it provides better or same solutions for almost all test problems than the heuristic in Gupta et al.(1990).
Abstract
This paper addresses the problem of minimizing the mean squared deviation(MSD) of completion times from a common due date in unconstrained case. The unconstrained MSD is known to be NP-complete and a heuristic algorithm which consists of two phases(schedule construction and improvement) is proposed. In the schedule construction phase, by using the simulated annealing technique and balanced V-shape schedule, good initial solutions are constructed. Then, the improvement phase enhances the quality of solution based on the concepts of both better dual and better pair. The developed two phases are serially employed to obtain the schedule of minimizing MSD problem. The first phase focuses on the finding of good initial solution and the second phase stresses on the improvement of solution quality. For the unconstrained MSD problem, the best known heuristic the algorithm is in Ventura and Weng(1995) and the algorithm in Gupta et al.(1990) finds fairly good solutions with much less computational time than one in Ventura and Weng(1995). The proposed heuristic finds all optimal solutions of the test problems in Eilon and Chowdhury(1977) and Gupta et al.(1990) with much less computational time compared with the heuristic in Ventura and Weng(1995). In order to show the performance of proposed heuristic in detail when job sizes are large, several test problems are generated. The computational results show that it provides better or same solutions for almost all test problems than the heuristic in Gupta et al.(1990).
참고문헌 (24)
- Bagchi, Uttaraya, "Minimizing Mean Squared Deviation of Completion Times about a Common Due Date", Management Science, 33, pp.894~906 (1987)
- Baker, Kenneth R, "Sequencing with Earliness and Tardiness Penalties: A Review", Operations Research, 38, pp.22~36 (1990)
- Bonomi, E, "The N-city Traveling Salesman Problem: Statistical Mechanics and Metropolis Algorithm", SIAM Review, 26, pp.551~568 (1983)
- Burkard, R. E, "A Thermodynamically Motivated Simulation Procedure for Combinatorial Optimization Problems", European Journal of Operational Research, 17, pp.169~174 (1984)
- Connolly,David T, "An Improved Annealing Scheme for the QAP", European Journal of Operational Research, 46, pp.93~100 (1990)
- De, Prabuddha, "On the Minimization of Completion Time Variance with a Bicriteria Extension", Operations Research, 40, pp.1148~1155 (1992)
- Eilon, Samuel, "Minimizing Waiting Time Variance in the Single Machine Problem", Management Science, 23, pp.567~575 (1977)
- Gupta, M. G, "Minimizing the Flow Time Variance in the Single Machine Systems", Journal of Operational Research Society, 41, pp.767~779 (1990)
- Hall, Nicholas G, "Proof of a Conjecture of Schrage about the Completion Time Variance Problem", Operations Research Letters, 10, pp.467~472 (1991)
- Kanet,John J, "Minimizing Variation of Flow Time in Single Machine Systems", Management Science, 27, pp.1453~1459 (1991)
- Kim, C, "Minimizing the Mean Squared Deviation from a Common Due Date: Unconstrained and Constrained Cases", Production Planning & Control, 7, pp.492~502 (1996)
- Kim, C, "Assignment Problem in Single Row and Double Rows Machine Layouts During Slow and Peak Period", Computers & Industrial Engineering, 30, pp.411~422 (1996)
- 김수행, "AHP를 이용한 도요타 생산시스템 평가항목의 중요도 분석 - 공급사슬망 위치에 따른 비교", 경영연구, 23(4), pp.137~161 (2008), 한국산업경영학회
- Kirkpatrick, S, "Optimization by Simulated Annealing", Science, 220, pp.671~680 (1983)
- Kouvelis, P, "A Simulated Annealing Procedure for Single Row Layout Problems in Flexible Manufacturing Systems", International Journal of Production Research, 30, pp.717~732 (1992)
- Kuiak,W, "Completion Time Variance Minimization on a Single Machine is Difficult", Operations Research Letters, 14, pp.49~59 (1993)
- Laarhoven, P. J, "Job Shop Scheduling by Simulated Annealing", Operations Research, 40, pp.113~125 (1992)
- Merten, Alan G, "Variance Minimization in Single Machine Sequencing Problems", Management Science, 18, pp.518~528 (1972)
- Raghavachari,M, "A V-shaped Property of Optimal Schedule of Jobs about a Common Due Date", European Journal of Operational Research, 23, pp.401~402 (1986)
- Schrage,Linus, "Minimizing the Time in System Variance for a Finite Job Set", Management Science, 21, pp.540~543 (1975)
- Sidney,Jeffrey B, "Optimal Single Machine Scheduling with Earliness and Tardiness Penalties", Operations Research, 25, pp.62~69 (1977)
- Vani, Vina, "Deterministic and Random Single Machine Sequencing with Variance Minimization", Operations Research, 35, pp.111~120 (1987)
- Ventura, Jose A, "Minimizing Single Machine Completion Time Variance", Management Science, 41, pp.1448~1455 (1995)
- 유승억, "JIT실행과 비전통적 성과측정 및 보상시스템 속성의 관련성에 관한 연구", 경영연구, 20(3), pp.291~317 (2005), 한국산업경영학회