[논문]다 단계 혼합흐름공정 일정계획에서 납기지연 작업 수의 최소화를 위한 대체 목적함수 기반 탐색기법

최현선; 김형원; 이동호

[국내논문] 다 단계 혼합흐름공정 일정계획에서 납기지연 작업 수의 최소화를 위한 대체 목적함수 기반 탐색기법
Surrogate Objective based Search Heuristics to Minimize the Number of Tardy Jobs for Multi-Stage Hybrid Flow Shop Scheduling 원문보기

대한산업공학회지 = Journal of the Korean Institute of Industrial Engineers, v.35 no.4, 2009년, pp.257 - 265

최현선 (한국능률협회컨설팅) , 김형원 (한양대학교 산업공학과) , 이동호 (한양대학교 산업공학과)

Abstract ▼ AI-Helper

This paper considers the hybrid flow shop scheduling problem for the objective of minimizing the number of tardy jobs. In hybrid flow shops, each job is processed through multiple production stages in series, each of which has multiple identical parallel machines. The problem is to determine the allocation of jobs to the parallel machines at each stage as well as the sequence of the jobs assigned to each machine. Due to the complexity of the problem, we suggest search heuristics, tabu search and simulated annealing algorithms with a new method to generate neighborhood solutions. In particular, to evaluate and select neighborhood solutions, three surrogate objectives are additionally suggested because not much difference in the number of tardy jobs can be found among the neighborhoods. To test the performances of the surrogate objective based search heuristics, computational experiments were performed on a number of test instances and the results show that the surrogate objective based search heuristics were better than the original ones. Also, they gave the optimal solutions for most small-size test instances.

Keyword

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

가설 설정

Also, each operation of a job has the same processing time on each parallel machine since we consider identical parallel machines at each stage. Other assumptions made for the problem considered here are: (a) each machine can process only one job at a time and each job can be processed only on a machine at each stage; (b) setup times for the jobs are sequence-independent and hence can be included in the corresponding processing times; (c) no job can be split and pre-em ptied; and (d) m achine breakdow ns are not considered.

제안 방법

To compare the performances of the search heuristics suggested in this paper, computational tests were done, and the results are reported in this section. We tested eight search heuristics, TS0 (SA0) without the surrogate objectives and TS1 (SA1), TS2 (SA2), TS3 (SA3) with the surrogate objectives of minimum tardiness, minimum mean tardiness, and maximum mean earliness, respectively. All the algorithms were coded in C and the tests were done on a workstation with an Intel Xeon processor operating at 3.
To find the appropriate values of the parameters, a preliminary experiment was done for each search heuristic type. For the TS algorithms, several values for the tabu list size (l) and LTS for the termination condition were tested on representative test instances, and they were set to 50 and 500, respectively.
The first test is on the comparison of the search heuristics with each other for multi-stage hybrid flow shops since the optimal solutions could not be obtained in a reasonable amount of computation time. The performance measures used are: (a) the relative performance ratio; and (b) CPU seconds.
) The performance measures are: (a) number of instances that each search heuristic gave the optimal solutions; and (b) CPU seconds. For this test, we used the 960 test instances of Choi and Lee (2009), i.e., 10 instances for each of 96 combinations of the number of machines (1, 2, 3 and 4 at the first stage and 2, 3 and 4 at the second stage), four levels of the number of jobs (10, 12, 14 and 15), and two levels of the due-date tightness (loose and tight).
This paper considered multi-stage hybrid flow shop scheduling, which can be found usually in the electronics industry as well as various traditional industries such as food, chemical and steel. The problem is to determine the allocation of jobs to parallel machines at each stage as well as the sequence of the jobs assigned to each machine for the objective of minimizing the number of tardy jobs. Due to the complexity of the problem, two types of search heuristics, tabu search and simulated annealing algorithms, were suggested with a hybrid neighborhood generation method.

대상 데이터

The second test was done for two-stage hybrid flow shops. In this test, TS3 and SA3 with the surrogate objective of maximum mean earliness were compared with the optimal branch and bound algorithm of Choi and Lee (2009).

이론/모형

Here, the interchange method generates a neighborhood solution by selecting two jobs in the current sequence and interchanging them, while the insertion method selects two jobs in the current sequence and removes the first job from the original place and inserting it to the position that directly precedes the second job. In this research, we use the hybrid method to generate neighborhood solutions as scattered as possible, called the diversification strategy in the literature. See Kim et al.
The problem is to determine the allocation of jobs to parallel machines at each stage as well as the sequence of the jobs assigned to each machine for the objective of minimizing the number of tardy jobs. Due to the complexity of the problem, two types of search heuristics, tabu search and simulated annealing algorithms, were suggested with a hybrid neighborhood generation method. In particular, surrogate objectives were additionally suggested to break ties among the neighborhood solutions with the same number of tardy jobs since the objective has the characteristic that not much difference can be found among the neighborhood solutions.

참고문헌 (28)

Azizoglu, M., Cakmak, E. and Kondakci, S. A. (2001), A flexible flow shop problem with total flow time minimization, European Journal of Operational Research, 132, 528-538

상세보기
Brah, S. A. and Hunsucker J. L. (1991), Branch and bound algorithm for the flow shop with multiple processors, European Journal of Operational Research, 51, 88-99

상세보기
Chen, B. (1995), Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at on stage, Journal of Operation Research Society, 46, 231-244
Choi, H.-S. and Lee, D.-H. (2007), A branch and bound algorithm for two-stage hybrid flow shops: minimizing the number of tardy jobs, Journal of the Korean Institute of Industrial Engineers, 33, 213-220
Choi, H.-S., Kim, H.-W., Lee, D.-H., Yun, J., Yoon, C. Y., and Chae, K. B. (2009), Scheduling algorithms for two-stage reentrant hybrid flow shops: minimizing makespan under the maximum allowable due-dates, International Journal of Advanced Manufacturing Technology, 42, 963-973

상세보기
Choi, H.-S. and Lee, D.-H. (2009), Scheduling algorithms to minimize the number of tardy jobs in two-stage hybrid flow shops, Computers and Industrial Engineering, 56, 113-120

상세보기
Fouad, R., Abdelhakim, A. and Salah, E. E. (1998), A hybrid three-stage flowshop problem: efficient heuristics to minimize makespan, European Journal of Operational Research, 109, 321-329

상세보기
Garey, M. R. and Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company
Glover, F. (1989), Tabu search: part I, ORSA Journal of Computing, 1, 190-206

상세보기
Glover, F., Laguna, M. (1993), Tabu search in Modern Heuristics Techniques for Combinatorial Problems, Blackwell Scientific Publications, Oxford, 70-141
Guinet, A. G. P. and Solomon, M. M. (1996), Scheduling hybrid flow shops to minimize maximum tardiness or maximum completion time, International Journal of Production Research, 34, 1643-1654

상세보기
Gupta, J. N. D. (1988), Two-stage hybrid flow shop scheduling problem, Journal of Operation Research Society, 39, 359-364

상세보기
Gupta, J. N. D. and Tunc, E. A. (1991), Scheduling for a two-stage hybrid flowshop with parallel machines at the second stage, International Journal of Production Research, 29, 1480-1502
Gupta, J. N. D. and Tunc, E. A. (1998), Minimizing tardy jobs in a two-stage hybrid flowshop, International Journal of Production Research, 36, 2397-2417

상세보기
Ho, J. C. and Chang, Y. L. (1995), Minimizing the number of tardy jobs for m parallel machines, European Journal of Operational Research, 84, 343-355

상세보기
Janiak, A., Kozan, E., Lichtenstein, M. and Oguz, C. (2007), Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion, International Journal of Production Economics, 105, 407-424

상세보기
Kemal, A., Orhan, E. and Alper, D. (2007), Using ant colony optimization to solve hybrid flow shop scheduling problems, International Journal of Advanced Manufacturing Technology, 35, 541-550

상세보기
Kim, S.-I., Choi, H,-S. and Lee, D.-H. (2007), Scheduling algorithms for parallel machines with sequence-dependent setup and distinct ready times: minimizing total tardiness, Proceedings of the Institution of Mechanical Engineers Part B: Journal of Engineering Manufacture, 221, 1087-1096

상세보기
Laguna, M., Barnes, J. W. and Glover, F. (1991), Tabu search methods for a single machine scheduling problem, Journal of Intelligent Manufacturing, 2, 63-74

상세보기
Lee, C. Y. and Vairaktarakis, G. L. (1994), Minimizing makespan in hybrid flow shops, Operations Research Letters, 16, 149-158

상세보기
Lee, G.-C. (2006), Scheduling methods for a hybrid flowshop with dynamic order arrival, Journal of the Korean Institute of Industrial Engineers, 32, 373-381
Lee, G.-C. and Kim, Y.-D. (2004), A branch-and-bound algorithm for a two-stage hybrid flow shop scheduling problem minimizing total tardiness, International Journal of Production Research, 42, 4731-4743

상세보기
Lee, G.-C., Kim, Y.-D. and Choi, S.-W. (2004), Bottleneck-focused scheduling for a hybrid flow shop, International Journal of Production Research, 42, 165-181

상세보기
Lee, J. S. and Park, S. H. (1999), Scheduling heuristics for a two-stage hybrid flowshop with nonidentical parallel machines, Journal of the Korean Institute of Industrial Engineers, 25, 254-265
Linn, R. and Zhang, W. (1999), Hybrid flow shop scheduling, Computers and Industrial Engineering, 37, 57-61

상세보기
Mourisli, O. and Pochet, Y. (2000), A branch-and-bound algorithm for the hybrid flow shop, International Journal of Production Research Economics, 64, 113-125

상세보기
Park, M.-W. and Kim, Y.-D. (1998), A systematic procedure for setting parameters in simulated annealing algorithms, Computers and Operations Research, 25, 207-217

상세보기
Tsubone, H., Ohba, M., and Uetake, T. (1996), The impact of lot sizing and sequencing on manufacturing performance in a two-stage hybrid flow shop, International Journal of Production Research, 34, 3037-3053

상세보기

저자의 다른 논문 :

LOADING...

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증