[Back to Results | New Search]

Student Number 954306002 Author Yu-jen Kung(龔裕仁) Author's Email Address nelson.kung@snptaiwan.com Statistics This thesis had been viewed 1556 times. Download 644 times. Department Executive Master of Industrial Management Year 2007 Semester 2 Degree Master Type of Document Master's Thesis Language zh-TW.Big5 Chinese Title A single machine scheduling problem with consideration of sequence-dependent setup time and multiple objectives Date of Defense 2008-05-07 Page Count 91 Keyword Makespan Sequence-dependent setup time Total tardiness Abstract This research mainly focuses on production scheduling related theories and analyze related industrial environment of case company. The objectives are to define suitable logic and to find out the special rules for case company. The most important characteristic in this case is the sequence-dependent setup time for production. We investigate and develop the solution and criterion for our case company. Moreover, we also consider the times of raw materials arrival and expiration date limit of raw materials stocked in this problem. The objectives need simultaneously consider Makespan and total tardiness. These two criteria are often mutually conflict in scheduling. The choice of criteria will depends on company’s business goal and market demand changed. Therefore, single solution for scheduling does not conform to the actual demand.

We use a deterministic model of single machine scheduling problem with consideration of sequence-dependent setup time and multiple objectives. We develop three special algorithms for case company and study their efficiency by experiment using the historical data. The first heuristic algorithm was based on simple dispatching rules of SST and SPT and try to find a near optimal makespan solution. The second heuristic is to find a near-optimal total tardiness solution based on simple dispatching rules of EDD, SST, and SPT. The last heuristic is to find a near Pareto-optimal solution by combining the first two algorithms. Our experimental results show that this model achieved our expectative and also has good solution quality. The algorithms we developed could be used to solve this kind of scheduling problem well and make contributions to enterprise's benefit.Table of Content 第 一 章:緒論....1

第 二 章:文獻探討....5

第 三 章:個案公司排程問題分析.....26

第 四 章:模型.....32

第 五 章:啟發式演算法架構與建置.....48

第 六 章:結論與未來研究方向......75

參考文獻.....78

附錄一 實驗結果的訂單置換時間列表......83

附錄二 實驗排程結果的各種細項列表......84Reference [1] Asano, M. and Ohta, H., “Single Machine Scheduling Using Dominance Relation to Minimize Earliness Subject to Ready and Due times,” International Journal of Production Research, Vol.44, pp.35-43 (1996).

[2] Baker, K.R., “Heuristic Procedures for Scheduling Job Families with Setups and Due Dates,” Naval Research Logistics, Vol.46, pp.978-991 (1999).

[3] Barnes, J.W. and Vanston, L.K., “Scheduling Jobs with Linear Delay Penalties and Sequence Dependent Setup Costs,” Operations Research, Vol.29, pp.146-160 (1981).

[4] Bianco, L., Ricciardelli, S., Rinaldi, G. and Sassano, A., “Scheduling Tasks with Sequence-Dependent Processing Times,” Naval Research Logistics, Vol.35, pp.177-184 (1988).

[5] Bruno, J. and Downey, P., “Complexity of Task Sequencing with Deadline, Setup Times and Changeover Costs,” SIAM Journal on Computing, Vol.7, pp.393-404 (1978).

[6] Burstall, R.M., “A Heuristic Method for a Job-Shop Scheduling Problem,” Operations Research, Vol.17, pp.291-304 (1966).

[7] Buzacott, J.A. and Dutta, S.K., “Sequencing Many Jobs on a Multi-Purpose Facility,” Naval Research Logistics Quarterly, Vol.18, pp.75-82 (1971).

[8] Conway, R.W., Maxwell, W.L. and Miller, L.W., Theory of Scheduling, Addison Wesley, Massachusetts, (1967).

[9] Driscoll, W.C. and Emmons, H., “Scheduling Production on One Machine with Changeover Costs,” IIE Transactions, Vol.9, pp.388-395 (1997).

[10] Farn, C.D. and Muhlemann, A.P., “The Dynamic Aspects of a Production Scheduling Problem,” International Journal of Production Research, Vol.17, pp.15-21 (1979).

[11] Feo, T.A., Sarathy, K. and McGahan, J., “A Grasp for Single Machine Scheduling with Sequence Dependent Setup Costs and Linear Delay Penalties,” Computers & Operations Research, Vol.23, pp.881-895 (1996).

[12] Gilmore, P.C. and Gomory, R.E., “Sequencing a One-state Variable Machine; A Solvable Case of the Traveling Salesman Problem,” Operations Research, Vol.12, pp.655-679 (1964).

[13] Glover, F., “Tabu Search-Part I,” ORSA Journal on Computing, Vol.1, pp.4-32 (1990).

[14] Glover, F., “Tabu Search-Part II,” ORSA Journal on Computing, Vol.2, pp.4-32 (1990).

[15] Haynes, R.D., Komar, C.A. and Byrd, J., “The Effectiveness of Three Heuristic Rules for Job Sequencing in a Single Production Facility,” Management Science, Vol.9, pp.575-580 (1973).

[16] He, W. and Kusiak, A., “Scheduling Manufacturing Systems,” Computers in Industry, Vol.20, pp.163-175 (1992).

[17] Holland, J.H., “Genetic Algorithms and the Optimal Allocation of Trials,” SIAM Journal on Computing, Vol.2, pp.99-105 (1973)

[18] Kaneko, E., Liquid Crystal Display, KTK Scientific, Tokyo, (1987).

[19] Kim, S.Y., Lee, Y.H. and Agnihotri, D., “A Hybrid Approach to Sequencing Jobs Using Heuristic Rules and Neural Networks,” Production Planning & Control, Vol.6, pp.445-454 (1995).

[20] Kirckpatrick, S., Gelatt, C.D. and Vecchi, M.P., “Optimization by Simulated Annealing,” Science, Vol.220, pp.671-689 (1983).

[21] Krajewski, L.J., et al. “Kanban, MRP, and shaping the manufacturing environment,” Manage Science, Vol.33, pp.39-57 (1987).

[22] Kusiak, A. and Finke, G., “Modeling and Solving the Flexible Forging Module Scheduling Problem,” Engineering Optimization, Vol.12, pp.1-12 (1987).

[23] Laguna, M., Barnes, J.W. and Glover, F.W., “Tabu Search Methods for a Single-Machine Scheduling Problem,” Journal of Intelligent Manufacturing, Vol.2, pp.63-74 (1991).

[24] Lawler, E.L., Lenstra, J.K., Rinnooy, K.A. And Shmoys, D.B., Sequencing and Scheduling: Algorithms and Complexity. In Logistics of Production a-nd Inventory, Amsterdam, Netherlands: North Holland, (1993).

[25] Lee, Y.H., Bhaskaran, K. and Pinedo, M., “A Heuristic to minimize the Total Weighted Tardiness with Sequence Dependent Setups,” IIE Transactions, Vol.29, pp.45-52 (1997).

[26] Lockett, A.G. and Muhlemann, A.P., “A Scheduling Problem Involving Sequence Dependent Changeover Costs,” Operations Research, Vol.20, pp.895-902 (1972).

[27] Monma, C.L. and Potts, C.N., “On the Complexity of Scheduling with Batch Setup Times,” Operations Research, Vol.37, pp.798-804 (1989).

[28] Moore, J.E., “An Algorithm for a Single-Machine Scheduling Problem with Sequence-Dependent Setup Times and Scheduling Windows,” IIE Transactions, Vol.7, pp.35-41 (1975).

[29] Ovacik, I.M. and Uzsoy, R., “Rolling Horizon Algorithms for a Single-Machine Dynamic Scheduling Problem with Sequence-Dependent Setup Times,” International Journal of Production Research, Vol.32, pp.1243-1263 (1994).

[30] Parker, R.G.., Deterministic Scheduling Theory, Chapman and Hall, London, (1995).

[31] Picard, J.C. and Queyranne, M., “The Time-Dependent Traveling Salesman Problem and its Application to The Tardiness Problem in One Machine Scheduling,” Operations Research, Vol.26, pp.86-110 (1978).

[32] Pinedo, M., Scheduling: Theory, algorithms, and systems, Prentice Hall, New Jersey, (1995).

[33] Rubin, P.A. and Ragatz, G.L., “Scheduling in a Sequence Dependent Setup Environment with Genetic Search,” Computers & operations research, Vol.22, pp.85-99 (1995).

[34] Sielken, R.L. Jr., “Sequencing with Set-up Costs by Zero-One Mixed Integer Linear Programming,” IIE Transactions, Vol.8, pp.369-371 (1976).

[35] Smith, W.E., “Various Optimizers for Single Stage Production,” Naval Research Logistics Quarterly, Vol.3, pp.59-66 (1956).

[36] Taha, H., “Sequencing by Implicit Ranking and Zero-One Polynomial Programming,” IIE Transactions, Vol.3, pp.299-301 (1971).

[37] Tan, K.C. and Narasimhan, R., “Multi-Objective Sequencing with Sequence Dependent Setup Times,” International Journal of Operations and Quantitative, Vol.3, pp.69-84 (1997).

[38] ten Kate, H.A., Wijngaard, J. and Zijm, W.H.M. “Minimizing Total Earliness, Tardiness, and Setup Costs,” School of Management and Organization, University of Groningen, Holland, Research Report No. RR, pp.1991-2012, (1991).

[39] Uzsoy, R., Martin-Vega, L.A., Lee, C.Y. and Leonard, P.A., “Production Scheduling Algorithms for a Semiconductor Test Facility,” IEEE transactions on semiconductor manufacturing, Vol.4, pp.270-280 (1991).

[40] Uzsoy, R., Lee, C. and Martin-Vega, A., “Scheduling Semiconductor Test Operations: Minimizing Maximum Lateness and Number of Tardy Jobs on a Single Machine,” Naval Research Logistics, Vol.39, pp.369-388 (1992).

[41] White, C.H. and Wilson, R.C., “Sequence Dependent Setup Times and Job Sequencing,” International Journal of Production Research, Vol.15, pp.191-202 (1977).

[42] Woodruff, D.L. and Spearman, M.L., “Sequencing and Batching for Two Classes of Job with Deadlines and Setup Times,” Production and Operations Management, Vol.1 pp.87-102 (1992).

[43] Yang, W.H. and Liao, C.J., “Survey of Scheduling Research Involving Setup Times,” International Journal of Systems Science, Vol.30, pp.143-155 (1999).Advisor Ying-chieh Yeh(葉英傑)

Files approve immediately

954306002.pdf Date of Submission 2008-05-14

Our service phone is (03)422-7151 Ext. 57407,E-mail is also welcomed.