臺灣博碩士論文加值系統

本研究提出了一個以Linear Ordering為基礎的MIP (Mixed Integer Programming)模型，以及兩個改良模型來求解群組排程問題(Family Scheduling Problems)。本研究所求解的問題需考量不同群組工作之間切換時所產生的非相依群組整備時間，以及單機作業環境，分別以最小化總加權完工時間、最小化最大延遲時間以及最小化總加權延遲時間作為目標進行求解。並且，與以Manne的模型為基礎的MIP模型及其改良模型進行求解效能的比較。結果指出，本研究所提出來的改良模型有較好的效能。

In this research, an MIP (Mixed Integer Programming) formulation and its two adapted formulations are proposed. These three formulations based on linear ordering formulation are formulated to solve scheduling problems on single machine with independent family setup times. Three objectives for our problems solved are minimizing total weighted completion time, minimizing maximum lateness and minimizing total weighted tardiness respectively. Then, the computational performance of these three formulations are compared with the formulations based on Manne. The adapted formulation proposed performs efficiently.

摘要 i
ABSTRACT ii
誌謝 iii
Contents iv
List of Tables vi
List of Figures vii
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Purpose of Research 1
1.3 Literature Review 2
1.3.1 Family Scheduling 2
1.3.2 Mixed Integer Programming Formulations for Scheduling Problems 3
Chapter 2 MIP Formulations 8
2.1 Problem Statement 8
2.2 Problem Assumptions 8
2.3 Notation 9
2.3.1 Sets and Indices 9
2.3.2 Parameters 9
2.3.3 Variables 9
2.4 Formulations 10
2.4.1 Linear Ordering Formulation Constraints (LO) 10
2.4.1.1 Linear Ordering Formulation with SWPT or EDD ( ) 14
2.4.2 Adapted Linear Ordering Formulation Constraints (ALO) 14
2.4.3 Disjunctive Formulation Constraints (DJ) 16
2.4.3.1 Disjunctive Formulation with SWPT or EDD ( ) 18
Chapter 3 Computational Results 19
3.1 Parameters Design 19
3.2 Computational Performance 20
3.2.1 Performance for the Total Weighted Completion Time Problem 21
3.2.1.1 Comparison Based on Job-size 25
3.2.1.2 Comparison Based on Class 25
3.2.1.3 Summary for the Total Weighted Completion Time Problems 26
3.2.2 Performance for the Maximum Lateness Problems 34
3.2.2.1 Comparison Based on Job-size 34
3.2.2.2 Comparison Based on Class 35
3.2.2.3 Summary for the Maximum Lateness Problems 36
3.2.3 Performance for the Total Weighted Tardiness Problems 42
3.2.3.1 Comparison Based on Job-size 42
3.2.3.2 Comparison Based on Class 42
3.2.3.3 Summary for the Total Weighted Tardiness Problems 43
3.3 Another Computational Experiment 46
Chapter 4 Conclusions 48
Reference 49

[1]Allahverdi, A., Gupta, J. N., & Aldowaisan, T. (1999). A review of scheduling research involving setup considerations. Omega, 27(2), 219-239.
[2]Allahverdi, A., Ng, C. T., Cheng, T. E., & Kovalyov, M. Y. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187(3), 985-1032.
[3]Ascheuer, N., Fischetti, M., & Grötschel, M. (2001). Solving the asymmetric travelling salesman problem with time windows by branch-and-cut.Mathematical Programming, 90(3), 475-506.
[4]Baker, K. R., & Keller, B. (2010). Solving the single-machine sequencing problem using integer programming. Computers & Industrial Engineering, 59(4), 730-735.
[5]Baker, K. R., & Magazine, M. J. (2000). Minimizing maximum lateness with job families. European Journal of Operational Research, 127(1), 126-139.
[6]Balas, E. (1985). On the facial structure of scheduling polyhedra. InMathematical Programming Essays in Honor of George B. Dantzig Part I (pp. 179-218). Springer Berlin Heidelberg.
[7]Ballicu, M., Giua, A., & Seatzu, C. (2002, October). Job-shop scheduling models with set-up times. In Systems, Man and Cybernetics, 2002 IEEE International Conference on (Vol. 5, pp. 6-pp). IEEE.
[8]Blazewicz, J., Dror, M., & Weglarz, J. (1991). Mathematical programming formulations for machine scheduling: a survey. European Journal of Operational Research, 51(3), 283-300.
 
[9]Bruno, J., & Sethi, R. (1976, October). Task sequencing in a batch environment with setup times. In Proceedings of the International Workshop organized by the Commision of the European Communities on Modelling and Performance Evaluation of Computer Systems (pp. 81-88). North-Holland Publishing Co..
[10]Choi, I. C., & Choi, D. S. (2002). A local search algorithm for jobshop scheduling problems with alternative operations and sequence-dependent setups. Computers & Industrial Engineering, 42(1), 43-58.
[11]Crauwels, H. A. J., Potts, C. N., & Van Wassenhove, L. N. (1997). Local search heuristics for single machine scheduling with batch set-up times to minimize total weighted completion time. Annals of Operations Research, 70, 261-279.
[12]Dunstall, S., Wirth, A., & Baker, K. R. (2000). Lower bounds and algorithms for flowtime minimization on a single machine with set-up times. Journal of Scheduling, 3(1), 51-69.
[13]Dyer, M. E., & Wolsey, L. A. (1990). Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Applied Mathematics, 26(2), 255-270.
[14]Eren, T., & Güner, E. (2006). A bicriteria scheduling with sequence-dependent setup times. Applied Mathematics and Computation, 179(1), 378-385.
[15]Keha, A. B., Khowala, K., & Fowler, J. W. (2009). Mixed integer programming formulations for single machine scheduling problems. Computers & Industrial Engineering, 56(1), 357-367.
[16]Larsen, J. (1999). Parallelization of the vehicle routing problem with time windows (Doctoral dissertation, Technical University of DenmarkDanmarks Tekniske Universitet, Department of Informatics and Mathematical ModelingInstitut for Informatik og Matematisk Modellering).
[17]Maffioli, F., & Sciomachen, A. (1997). A mixed-integer model for solving ordering problems with side constraints. Annals of Operations Research, 69, 277-297.
[18]Manne, A. S. (1960). On the job-shop scheduling problem. Operations Research, 8(2), 219-223.
[19]Monma, C. L., & Potts, C. N. (1989). On the complexity of scheduling with batch setup times. Operations Research, 37(5), 798-804.
[20]Nemhauser, G. L., & Savelsbergh, M. W. (1992). A cutting plane algorithm for the single machine scheduling problem with release times. In Combinatorial Optimization (pp. 63-83). Springer Berlin Heidelberg.
[21]Nogueira, T. H., de Carvalho, C. R. V., & Ravetti, M. G. (2014). Analysis of mixed integer programming formulations for single machine scheduling problems with sequence dependent setup times and release dates.Optimization Online.
[22]Parsamanesh, A. H., & Sahraeian, R. (2015). Solving Single Machine Sequencing to Minimize Maximum Lateness Problem Using Mixed Integer Programming. Journal of Quality Engineering and Production Optimization,1(1), 33-42.
[23]Potts, C. N. (1980). An algorithm for the single machine sequencing problem with precedence constraints. In Combinatorial Optimization II (pp. 78-87). Springer Berlin Heidelberg.
[24]Queyranne, M. (1993). Structure of a simple scheduling olyhedron.Mathematical Programming, 58(1-3), 263-285.
[25]Ríos-Mercado, R. Z., & Bard, J. F. (2003). The flow shop scheduling polyhedron with setup times. Journal of Combinatorial Optimization, 7(3), 291-318.
 
[26]Rocha, P. L., Ravetti, M. G., Mateus, G. R., & Pardalos, P. M. (2008). Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times. Computers & Operations Research, 35(4), 1250-1264.
[27]Schutten, J. M. J., Van de Velde, S. L., & Zijm, W. H. M. (1996). Single-machine scheduling with release dates, due dates and family setup times.Management Science, 42(8), 1165-1174.
[28]Sousa, J. P., & Wolsey, L. A. (1992). A time indexed formulation of non-preemptive single machine scheduling problems. Mathematical programming, 54(1-3), 353-367.
[29]Van Eijl, C. A. (1995). A polyhedral approach to the delivery man problem. Department of Math. and Computing Science, University of Technology.
[30]Wagner, H. M. (1959). An integer linear‐programming model for machine scheduling. Naval Research Logistics Quarterly, 6(2), 131-140.
[31]Webster, S., & Baker, K. R. (1995). Scheduling groups of jobs on a single machine. Operations Research, 43(4), 692-703.
[32]Williams, D., & Wirth, A. (1996). A new heuristic for a single machine scheduling problem with set-up times. Journal of the Operational Research Society, 47(1), 175-180.
[33]Zhu, Z., & Heady, R. B. (2000). Minimizing the sum of earliness/tardiness in multi-machine scheduling: a mixed integer programming approach. Computers & Industrial Engineering, 38(2), 297-305.