在群組生產特性(Group Technology, GT)下，族群內外皆具整備時間順序相依性(Sequence-Dependent Setup Times, SDST)之單機排程問題(Single-Machine Scheduling Problems, SMSP)中，本研究以實際印刷電路板製造業(Printed Circuit Boards Manufacturing)的表面貼焊製程(Surface Mount Technology, SMT)產線為例，在已將工件群組，且特定工件間具有優先限制的情況下，以最小總整備時間為目標式，針對族群及族群內工件的單機排程進行求解。
本研究先將此問題分成族群內及族群間兩個子問題，建立數學模型求解。之後建立在原混合啟發式演算法下，提出一套候選混合啟發式演算法，設計一套候選體制，能夠在合理的時間內提升最佳解的搜尋能力。且在族群內排程中，利用能快速減少族群內整備時間的啟發式方法產生初始解。最後將候選混合啟發式演算法、CPLEX兩階段求解與原混合啟發式演算法進行比較。
研究結果顯示，候選混合啟發式演算法在針對不同大小的工單中，皆能在合理的時間內找到比上述其他方法更好的解，故能夠實際應用到排程當中。

In the single-machine scheduling problems (SMSP) with group technology (GT) and both intra-family and inter-family sequence-dependent setup times (SDST), this study stems from Surface Mount Technology (SMT) production line of Printed Circuit Boards (PCBs) manufacturing company. All the jobs within each family are given, and also the precedence constraints are considered, the aim of this problem is to minimize the total setup times with intra-family and inter-family SDST in SMSP.
To begin with, the problem is divided into two sub-problems, the intra-family and the inter-family, and mathematical models are established to solve it. Then, based on original hybrid metaheuristics, hybrid metaheuristic with candidate design is developed to solve this problem, which can improve the search ability of the optimal solution in a reasonable time. In intra-family scheduling, to generate the initial solutions within each family, a setup time-based heuristic is developed. Finally, candidate hybrid metaheuristics are compared with two-stage mathematical model and original hybrid metaheuristics.
The results show that candidate hybrid metaheuristics can find better solutions than the other methods mentioned above for different-sized instances in a reasonable CPU time. Therefore, it can be practically applied to the real-life scheduling.

Allahverdi, A., Gupta, J. N., & Aldowaisan, T. (1999). A review of scheduling research involving setup considerations. Omega, 27(2), 219-239.
Allahverdi, A., & Soroush, H. (2008). The significance of reducing setup times/setup costs. European Journal of Operational Research, 187(3), 978-984.
Azadeh, A., Keramati, A., Karimi, A., & Moghaddam, M. (2010). A multi-objective genetic algorithm for scheduling optimisation of m job families on a single machine. International Journal of Industrial and Systems Engineering, 6(4), 417-440.
Avalos-Rosales, O., Angel-Bello, F., & Alvarez, A. (2015). Efficient metaheuristic algorithm and re-formulations for the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times. The International Journal of Advanced Manufacturing Technology, 76(9-12), 1705-1718.
Cheng, T. E., Janiak, A., & Kovalyov, M. Y. (2001). Single machine batch scheduling with resource dependent setup and processing times. European Journal of Operational Research, 135(1), 177-183.
Chang, P.-C., Hsieh, J.-C., & Wang, Y.-W. (2003). Genetic algorithms applied in BOPP film scheduling problems: minimizing total absolute deviation and setup times. Applied Soft Computing, 3(2), 139-148.
Chen, T., Long, L., & Fung, R. Y. (2006). A genetic algorithm for the batch scheduling with sequence-dependent setup times Intelligent computing in signal processing and pattern recognition (pp. 1137-1144): Springer.
Gary, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness.
Herr, O., & Goel, A. (2016). Minimizing total tardiness for a single machine scheduling problem with family setups and resource constraints. European Journal of Operational Research, 248(1), 123-135.
Hinder, O., & Mason, A. J. (2017). A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness. European Journal of Operational Research, 262(2), 411-423.
Jin, F., Song, S., & Wu, C. (2009). A simulated annealing algorithm for single machine scheduling problems with family setups. Computers & Operations Research, 36(7), 2133-2138.
Jin, F., Gupta, J. N., Song, S., & Wu, C. (2010). Single machine scheduling with sequence-dependent family setups to minimize maximum lateness. Journal of the Operational Research Society, 61(7), 1181-1189.
Karabatı, S., & Akkan, C. (2006). Minimizing sum of completion times on a single machine with sequence-dependent family setup times. Journal of the Operational Research Society, 57(3), 271-280.
Keshavarz, T., Savelsbergh, M., & Salmasi, N. (2015). A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties. Applied mathematical modelling, 39(20), 6410-6424.
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H., & Shmoys, D. B. (1986). Erratum: The traveling salesman problem: A guided tour of combinatorial optimization. Journal of the Operational Research Society, 37(6), 655-655.
Lawler, E. L., Lenstra, J. K., Kan, A. H. R., & Shmoys, D. B. (1993). Sequencing and scheduling: Algorithms and complexity. Handbooks in operations research and management science, 4, 445-522.
Li, L., & Qiao, F. (2008). ACO-based scheduling for a single batch processing machine in semiconductor manufacturing. Paper presented at the 2008 IEEE International Conference on Automation Science and Engineering.
Mosheiov, G., & Oron, D. (2006). Single machine scheduling with batch-dependent setup times. Information processing letters, 98(2), 73-78.
Nowicki, E., & Zdrzałka, S. (1996). Single machine scheduling with major and minor setup times: a tabu search approach. Journal of the Operational Research Society, 47(8), 1054-1064.
Ozgur, C., & Brown, J. (1995). A two-stage traveling salesman procedure for the single machine sequence-dependent scheduling problem. Omega, 23(2), 205-219.
Ozgur, C. O., & Bai, L. (2010). Hierarchical composition heuristic for asymmetric sequence dependent single machine scheduling problems. Operations Management Research, 3(1), 98-106.
Pei, J., Liu, X., Pardalos, P. M., Fan, W., & Yang, S. (2017). Scheduling deteriorating jobs on a single serial-batching machine with multiple job types and sequence-dependent setup times. Annals of Operations Research, 249(1), 175-195.
Pinheiro, J. C., & Arroyo, J. E. C. (2020). Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints. Annals of Mathematics and Artificial Intelligence, 88(1), 169-185.
Rego, M. F., Souza, M. J. F., & Arroyo, J. E. C. (2012). Multi-objective algorithms for the single machine scheduling problem with sequence-dependent family setups. Paper presented at the 2012 31st International Conference of the Chilean Computer Science Society.
Schaller, J. E., Gupta, J. N., & Vakharia, A. J. (2000). Scheduling a flowline manufacturing cell with sequence dependent family setup times. European Journal of Operational Research, 125(2), 324-339.
Sels, V., & Vanhoucke, M. (2012). A hybrid genetic algorithm for the single machine maximum lateness problem with release times and family setups. Computers & Operations Research, 39(10), 2346-2358.
Suppiah, Y., & Omar, M. K. (2014). A hybrid tabu search for batching and sequencing decisions in a single machine environment. Computers & Industrial Engineering, 78, 135-147.
Taner, M. R., Hodgson, T. J., King, R. E., & Schultz, S. R. (2007). Satisfying due-dates in the presence of sequence dependent family setups with a special comedown structure. Computers & Industrial Engineering, 52(1), 57-70.
Vilar Jacob, V., & Arroyo, J. E. C. (2016). ILS Heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness. Journal of Applied Mathematics, 2016.
Zhu, X., & Wilhelm, W. E. (2006). Scheduling and lot sizing with sequence-dependent setup: A literature review. IIE transactions, 38(11), 987-1007.