臺灣博碩士論文加值系統

在生產排程問題中，工作或訂單順序代表其在機器上之處理先後順序，而排程則是明確排定每一工作或訂單在各台機器上之開始與完工時間。對某些排程問題而言，工作順序的給定並不直接等同排程結果。在這類型的問題中，除了排序之外，尚有諸如批量、交織穿插、延後執行等決策問題需要考量。這類型的排程問題即使固定其工作順序仍值得探究。在給定工作順序後，這類型的排程問題可稱之為固定工作順序條件排程問題。本論文針對三個固定工作順序條件排程問題進行研究。

本論文首先探究之固定工作順序條件排程議題為兩階段組裝線流線型機組批量排程問題。此問題考量的組裝線流線型機組環境為：階段一配置 $m$ 台平行指定機器、階段二配置一台批量處理機器。給定 $n$ 筆工作或訂單順序，並考量總完工時間最小化的目標下，本研究提出一個 $O(mn+n^5)$ 時間複雜度之演算法。

第二個研究主題為兩階段差異化流線型機組排程問題。此問題考慮的差異化流線型機組環境為：階段一配置一台公用機器、階段二配置 $m$ 台平行指定機器。假設階段二的某平行指定機器 $M_l$ 擁有 $n_l$ 筆工作或訂單待處理。在分別給定 $m$ 台平行指定機器個別之工作或訂單順序，並考量總完工時間最小化的目標下，本研究提出一個 $O(m^2 rod_{l=1}^m n_l^{m+1})$ 時間複雜度之動態規劃演算法。

第三個研究議題為單機器雙子作業排程問題。此問題的工作或訂單皆為雙子作業，每個工作的兩個子作業間存在一個固定的延遲時間。本研究之目標為固定工作順序條件下最大完工時間最小化。關於此議題下的固定工作順序條件排程問題，其時間複雜度仍懸而未決，然本研究提出一個 $O(n^2)$ 時間複雜度演算法解決固定“子作業”順序條件排程問題。此外，三個多項式時間可解的特例狀況亦在本文中被提出探討。

In machine or shop scheduling, sequences of jobs or operations indicate the order of processing on machines while schedules explicitly specify the starting and completion times of activities on specific machines. For some problems, determining an optimal schedule from a given sequence may not be straightforward because another decision such as batching, interleaving, or idle time insertion is needed for optimality. In this study, three fixed-job-sequence problems are considered.

The first addressed problem is a two-stage assembly-type flowshop scheduling problem with batching considerations subject to a fixed job sequence. The assembly-type flowshop consists of $m$\ parallel dedicated machines at stage 1 and a batch machine at stage 2. The objective is to minimize the total completion time. A two-phase algorithm is developed to solve the studied problem in $O(mn+n^5)$\ time, where $n$\ is the number of jobs and $m$\ is the number of parallel dedicated machines arranged at stage 1.

In the second problem, total completion time minimization in a two-stage differentiation flowshop subject to fixed sequences of jobs per type is studied. The two-stage differentiation flowshop comprises a stage-1 common machine and $m$\ stage-2 parallel dedicated machines. The goal is to determine an optimal interleaved processing sequence of all jobs at stage 1. This study presents an $O(m^2 rod_{l=1}^m n_l^{m+1})$\ dynamic programming algorithm, where $n_l$\ is the number of type-$l$\ jobs. The running time is polynomial when $m$\ is constant.

In the third problem, the single-machine coupled-task scheduling, where the two tasks of each job are separated by an exact delay, is investigated. The aim is to schedule these coupled tasks to minimize the makespan subject to a given job sequence. Several intriguing properties of the studied problem are introduced. While the complexity status of the fixed-job-sequence problem remains open, an $O(n^2)$\ algorithm is proposed to construct a feasible schedule attaining the minimum makespan for a given permutation of $2n$\ tasks abiding by the fixed-job-sequence constraint. Three polynomially solvable cases and a complexity graph of the fixed-job-sequence problem are presented.

Abstract (in Chinese) i
Abstract (in English) iii
Acknowledgments (in Chinese) v
Acknowledgments (in English) vii
1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 State of the Art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Research Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Two-Stage Assembly-Type Flowshop Batch Scheduling 7
2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Two-Phase Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Two-Stage Differentiation Flowshop Scheduling 18
3.1 Problem Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 The Proposed Dynamic Program . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4 Single-Machine Coupled-Task Scheduling 30
4.1 General Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.3 Scheduling of Plausible Task Sequences . . . . . . . . . . . . . . . . . . . . 37
4.4 Polynomially Solvable Cases . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.4.1 1|(pj ; pj ; pj); fjs|Cmax . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.4.2 1|(p; p; bj); fjs|Cmax . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.4.3 1|(p; l; p); fjs|Cmax . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5 Concluding Remarks 54
5.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.2 Suggestions for Further Studies . . . . . . . . . . . . . . . . . . . . . . . . 55
Bibliography 56

Ageev, A.A., & Baburin, A.E. (2007). Approximation algorithms for UET scheduling
problems with exact delays. Operations Research Letters, 35(4), 533–540.
Ageev, A.A., & Kononov, A.V. (2006). Approximation algorithms for scheduling problems
with exact delays. Lecture Notes in Computer Sciences, 4368, 1–14.
Ahmadi, J.H., Ahmadi, R.H., Dasu, S., & Tang, C.S. (1992). Batching and scheduling
jobs on batch and discrete processors. Operations Research, 40(4), 750–763.
Ahr, D., B´ek´esi, J., Galambos, G., Oswald, M., & Reinelt, G. (2004). An exact algorithm
for scheduling identical coupled tasks. Mathematical Methods of Operations Research,
59(2), 193–203.
Albers, S., & Brucker, P. (1993). The complexity of one-machine batching problems.
Discrete Applied Mathematics, 47(2), 87–107.
Allahverdi, A., Gupta, J.N.D., & Aldowaisan, T. (1999). A review of scheduling research
involving setup considerations. Omega, 27(2), 219–239.
Allahverdi, A., Ng, C.T., Cheng, T.C.E., & Kovalyov, M.Y. (2008). A survey of scheduling
problems with setup times or costs. European Journal of Operational Research, 187(3),
985–1032.
Baker, K.R., & Trietsch, D. (2009). Principles of Sequencing and Scheduling. John Wiley
& Sons.
Banderier, C., & Schwer, S.R. (2005). Why Delannoy’s numbers?. Journal of Statistical
Planning and Inference, 135(1), 40–54.
Baptiste, P. (2010). A note on scheduling identical coupled tasks in logarithmic time.
Discrete Applied Mathematics, 158(5), 583–587.
Bauman, J., & J´ozefowska, J. (2006). Minimizing the earliness-tardiness costs on a single
machine. Computers & Operations Research, 33(11), 3219–3230.
B´ek´esi, J., Galambos, G., Oswald, M., & Reinelt, G. (2009). Improved analysis of an
algorithm for the coupled task problem with UET jobs. Operations Research Letters,
37(2), 93–96.
Blazewicz, J., Ecker, K., Kis, T., Potts, C.N., Tanas, M., & Whitehead, J. (2010). Scheduling
of coupled tasks with unit processing times. Journal of Scheduling, 13(5), 453–461.
Cheng, T.C.E., Ding, Q., & Lin, B.M.T. (2004). A concise survey of scheduling with
time-dependent processing times. European Journal of Operational Research, 152(1),
1–13.
Cheng, T.C.E., Gupta, J.N.D., & Wang, G. (2000a). A review of flowshop scheduling
research with setup times. Production and Operations Management, 9(3), 262–282.
Cheng, T.C.E., & Kovalyov, M.Y. (1998). An exact algorithm for batching and scheduling
two part types in a mixed shop: A technical note. International Journal of Production
Economics, 55(1), 53–56.
Cheng, T.C.E., Lin, B.M.T., & Tian, Y. (2009). Scheduling of a two-stage differentiation
flowshop to minimize weighted sum of machine completion times. Computers &
Operations Research, 36(11), 3031–3040.
Cheng, T.C.E., Lin, B.M.T., & Toker, A. (2000b). Makespan minimization in the twomachine
flowshop batch scheduling problem. Naval Research Logistics, 47(2), 128–144.
Cheng, T.C.E., & Wang, G. (1998). Batching and scheduling to minimize the makespan
in the two-machine flowshop. IIE Transactions, 30(5), 447–453.
Cheng, T.C.E., & Wang, G. (1999). Scheduling the fabrication and assembly of components
in a two-machine flowshop. IIE Transactions, 31(2), 135–143.
Coffman, E.G., Nozari, A., & Yannakakis, M. (1989). Optimal scheduling of products
with two subassemblies on a single machine. Operations Research, 37(3), 426–436.
Colina, E.C., & Quinino, R.C. (2005). An algorithm for insertion of idle time in the
single-machine scheduling problem with convex cost functions. Computers & Operations
Research, 32(9), 2285–2296.
Davis, J.S., & Kanet, J.J. (1993). Single-machine scheduling with early and tardy completion
costs. Naval Research Logistics, 40(1), 85–101.
Davis, T. (2006). Catalan number. http://www.geometer.org/mathcircles/catalan.pdf.
Della Croce, F., & Trubian, M. (2002). Optimal idle time insertion in early-tardy parallel
machines scheduling with precedence constraints. Production Planning & Control,
13(2), 133–142.
Garey, M.R., & Johnson, D.S. (1979). Computers and Intractability: A Guide to the theory
of NP-Completeness. W.H. Freeman and Company: New York.
Garey, M.R., Tarjan, R.E., & Wilfong, G.T. (1988). One processor scheduling with symmetrical
earliness and tardiness penalties. Mathematics of Operations Research, 13(2),
330–348.
Glass, C.A., Potts, C.N., & Strusevich, A.V. (2001). Scheduling batches with sequential
job processing for two-machine flow and open shops. INFORMS Journal on Computing,
13(2), 120–137.
Hall, N.G., Laporte, G., Selvarajah, E., & Sriskandarajah, C. (2003). Scheduling and lot
streaming in flowshops with no-wait in process. Journal of Scheduling, 6(4), 339–354.
Hendel, Y., & Sourd, F. (2007). An improved earliness-tardiness timing algorithm. Com-
puters & Operations Research, 34(10), 2931–2938.
Herrmann, J.W., & Lee, C.Y. (1992). Three-machine look-ahead scheduling problems.
Research Report No. 92-93, Department of Industrial Engineering, University of Florida,
FL.
Hwang, F.J., Kovalyov, M.Y., & Lin, B.M.T. (2010a). Minimization of total completion
time in flowshop scheduling subject to fixed job sequences, in: Proceedings of 12th
International Workshop on Project Management and Scheduling, Tours, France, pp.
249–252.
Hwang, F.J., Kovalyov, M.Y., & Lin, B.M.T. (2010b). Total completion time minimization
in two-machine flow shop scheduling problems with a fixed job sequence. Manuscript
in revision with Discrete Optimization.
Hwang, F.J., & Lin, B.M.T. (2011). Coupled-task scheduling on a single machine
subject to a fixed job sequence, Computer & Industrial Engineering,
doi:10.1016/j.cie.2011.01.002.
Jackson, J.R. (1955). Scheduling a production line to minimize maximum lateness. Re-
search Report 43, Management Science Research Report, University of California, LA.
Johnson, S.M. (1954). Optimal two- and three-stage production schedules with setup
times included. Naval Research Logistics Quarterly, 1(1), 61–68.
Kanet, J.J., & Sridharan, V. (2000). Scheduling with inserted idle time: problem taxonomy
and literature review. Operations Research, 48(1), 99–110.
Kovalyov, M.Y., Potts, C.N., & Strusevich, V.A. (2004). Batching decisions for assembly
production systems. European Journal of Operational Research, 157(3), 620–642.
Kyparisis, G.J., & Koulamas, C. (2000). Flow shop and open shop scheduling with a
critical machine and two operations per job. European Journal of Operational Research,
127(1), 120–125.
Lee, C.Y., Cheng, T.C.E., & Lin, B.M.T. (1993). Minimizing the makespan in the 3-
machine assembly-type flowshop scheduling problem. Management Science, 39(5), 616–
625.
Lee, C.Y., Uzsoy, R., & Martin-Vega, L.A. (1992). Efficient algorithms for scheduling
semiconductor burn-in operations. Operations Research, 40(4), 764–775.
Li, H., & Zhao, H. (2007). Scheduling coupled-tasks on a single machine, in: Proceedings of
2007 IEEE Symposium on Computational Intelligence in Scheduling, Honolulu, Hawaii,
pp. 137–142.
Lin, B.M.T., & Cheng, T.C.E. (2002). Fabrication and assembly scheduling in a twomachine
flowshop. IIE Transactions, 34(11), 1015–1020.
Lin, B.M.T., & Cheng, T.C.E. (2005). Two-machine flowshop batching and scheduling.
Annals of Operations Research, 113(2), 149–161.
Lin, B.M.T., & Cheng, T.C.E. (2006). Two-machine flowshop scheduling with conditional
deteriorating second operations. International Transactions in Operational Research,
13(2), 91–98.
Lin, B.M.T., & Cheng, T.C.E. (2010). Scheduling with centralized and decentralized
batching policies in concurrent open shops. Naval Research Logistics, doi:
10.1002/nav.20437.
Lin, B.M.T., Cheng, T.C.E., & Chou, A.S.C. (2007). Scheduling in an assembly-type
production chain with batch transfer. Omega, 35(2), 143–151.
Lin, B.M.T., & Hwang, F.J. (2011). Total completion time minimization in a 2-stage differentiation
flowshop with fixed sequences per job type. Information Processing Letters,
111(5), 208–212.
Mosheiov, G., & Sarig, A. (2010). Minimum weighted number of tardy jobs on an m-
machine flowshop with a critical machine. European Journal of Operational Research,
201(2), 404–408.
Mosheiov, G., & Yovel, U. (2004). Comments on “Flow shop and open shop scheduling
with a critical machine and two operations per job”. European Journal of Operational
Research, 157(1), 257–261.
Ng, C.T., & Kovalyov, M.Y. (2007). Batching and scheduling in a multi-machine flow
shop. Journal of Scheduling, 10(6), 353–364.
Orman, A.J., & Potts, C.N. (1997). On the complexity of coupled-task scheduling. Discrete
Applied Mathematics, 72(2), 141–154.
Orman, A.J., Shahani, A.K., & Moore, A.R. (1998). Modelling for the control of a complex
radar system. Computers & Operations Research, 25(3), 239–249.
Pan, Y. & Shi, L. (2005). Dual constrained single machine sequencing to minimize total
weighted completion time. IEEE Transactions on Automation Science and Engineering,
2(4), 344–357.
Portougal V. (1997). Production scheduling in the snack-food industry. Interfaces, 27(6),
51–64.
Potts, C.N., & Kovalyov, M.Y. (2000). Scheduling with batching: A review. European
Journal of Operational Research, 120(2), 228–249.
Potts, C.N., Strusevich, V.A., & Tautenhahn, T. (2001). Scheduling batches with simultaneous
job processing for two-machine shop problems. Journal of Scheduling, 4(1),
25–51.
Shafransky, Y.M., & Strusevich, V.A. (1998). The open shop scheduling problem with a
given sequence of jobs on one machine. Naval Research Logistics, 45(7), 705–731.
Shapiro, R.D. (1980). Scheduling coupled tasks. Naval Research Logistics Quarterly, 27(3),
489–498.
Sherali, H.D., & Smith, J.C. (2005). Interleaving two-phased jobs on a single machine.
Discrete Optimization, 2(4), 348–361.
Sourd, F. (2005). Optimal timing of a sequence of tasks with general completion costs.
European Journal of Operational Research, 165(1), 82–96.
Szwarc, W., & Mukhopadhyay, S.K. (1995). Optimal timing schedules in earlinesstardiness
single machine sequencing. Naval Research Logistics, 42(7), 1109–1114.
Yu, W., Hoogeveen, H., & Lenstra, J.K. (2004). Minimizing makespan in a two-machine
flow shop with delays and unit-time operations is NP-hard. Journal of Scheduling, 7(5),
333–348.
Zhang, Y., Zhou, Z., & Liu, J. (2010). The production scheduling problem in a multi-page
invoice printing system. Computers & Operations Research, 37(10), 1814–1821.