在製造系統裡其中一個重要的目標為提升準時交貨率，但某些產業在實際進行加工之前，可能無法得知確切的加工時間為何。因此本研究考慮一可批次加工的機台，及數個不同種類的工件，其中不同種類的工件不能被同時加工，且工件有各自的交期日。本研究假設機台每一次的加工時間為獨立且服從常態分配的隨機變數，且相同種類的工件其加工時間擁有相同的平均數及標準差，本研究的目的為在實際進行加工之前，研究如何將不同交期日的工件分批並排列其加工順序，以達到最小化總期望延遲工件數。
對此，本研究提出三個修改自Balut演算法的啟發式演算法，應用至批量排程的問題上。啟發式演算法一為先將工件依其種類分批，分好批次後，可將批次視為工件，應用Balut的演算法排列加工順序。因為批次裡包含了數個交期日不同的工件，因此需設定批次的虛擬交期日(batch due date)，分別為將批次內所包含工件的最小交期日設為此批次的批次交期日(啟發式演算法1A)以及將批次內所包含工件交期日的平均值設為此批次的批次交期日(啟發式演算法1B)，然後再應用Balut的演算法排列批次的加工順序。啟發式演算法二及啟發式演算法三則是先應用Balut演算法排序所有工件，然後依序向前填補以形成批次。此時可能會有某些批次的批量大小未能滿足機台容量限制，因此除了原始的加工順序(啟發式演算法2A、3A)，還會考慮依據各個批次的批量大小重新排序(啟發式演算法2B、3B)。
在數值分析的部分將比較這三個演算法共六種不同設定間的差異，且由數據顯示出啟發式演算法1A、2B及3A始終無法有最好的績效，因此將之刪除，然後再針對另外三個演算法作不同參數的敏感度分析，可發現影響這三個演算法最主要因素在於機台的容量限制與各個種類工件的平均個數這兩個值的差異；當機台容量限制比各個種類工件的平均個數小很多時，則較適用於啟發式演算法1B，而當機台容量限制與各個種類工件的平均個數差不多時，則啟發式演算法2A、3B可能會較好。

In this research, we consider one batch processing machine and a number of different types of jobs in which jobs with different types cannot be processed in the same batch. We assume that the processing time of each batch are random variables following independently normal distribution, and the processing time of the same type of jobs have the same mean and standard deviation. The purpose of this research is to batch and sequence the batches before the actual processing, in order to minimize the expected number of tardy jobs.
In this regard, this research proposes three heuristic methods applied to the batch scheduling problem, which are extended from Balut’s algorithm. Heuristic method 1 first batch the jobs according to their type, then apply Balut’s algorithm to obtain the processing order of all the batches. In this case, each batch may contain more than one job, so we need to set a virtual due date to each batch (batch due date). There are two different settings of batch due date, the smallest job due date in each batch (heuristics method 1A) and the average due date of each batch (heuristics method 1B), and then we can apply Balut’s algorithm to sequence the batches. Heuristic method 2 and heuristic method 3 first apply Balut’s algorithm to sequence all the jobs, and then move the jobs forward to fill the machine’s capacity and form batches. In this case, there may be some batches failed to meet the capacity of the machine, so we consider two different ways of sequence which are the original processing sequence (heuristic method 2A, 3A), and rearrange the order of each batch based on batch size (heuristic method 2B, 3B).
In the numerical analysis, we compare three heuristic methods in different parameters settings, and the numeric results show that heuristic method 1A, 2B and 3A do not have the best performance, so being deleted, and then we do sensitivity analysis of different parameters to the heuristic method 1B, 2A and 3B. We find that the most important factor to influence the occasion of using these three heuristic methods is the gap between the machine’s capacity and the average number of jobs in each family. When the machine’s capacity is much larger than the average number of jobs in each family, heuristic method 1B can have better performance, but when the machine’s capacity has little difference with the average number of jobs in each family, heuristic method 2A, 3B may be better.

中文部分：
曹經世「隨機加工時間之批量排程」，清華大學碩士論文，2003。

英文部分：
Akker, M. and H. Hoogeveen. “Minimizing the number of late jobs in a stochastic setting using a chance constraint.” Journal of Scheduling 11(1): 59-69, 2008.
Azizoglu, M. and S. Webster. “Scheduling a batch processing machine with incompatible job families.” Computers & Industrial Engineering 39(3-4): 325-335, 2001.
Balut, S. J. “Scheduling to Minimize the Number of Late Jobs When Set-Up and Processing Times Are Uncertain.” Management Science 19(11): 1283-1288, 1973.
Boxma, O. J. and F. G. Forst. “Minimizing the expected weighted number of tardy jobs in stochastic flow shops.” Operations Research Letters 5(3): 119-126, 1986.
Brucker, P., A. Gladky, H. Hoogeveen, M.Y. Kovalyov, C.N. Potts, T. Tautenhahn, S.Velde. “Scheduling a batching machine.” Journal of Scheduling 1(1): 31-54, 1998.
Cai, X. and S. Zhou. “Scheduling stochastic jobs with asymmetric earliness and tardiness penalties.” Naval Research Logistics (NRL) 44(6): 531-557, 1997.
Crauwels, H. A. J., C. N. Potts, L. N. Van Wassenhove. “Local search heuristics for single-machine scheduling with batching to minimize the number of late jobs.” European Journal of Operational Research 90(2): 200-213, 1996.
Hariri, A. M. A. and C. N. Potts. “A branch and bound algorithm for the two-stage assembly scheduling problem.” European Journal of Operational Research 103(3): 547-556, 1997.
Hochbaum, D. S. and D. Landy. “Scheduling with batching: minimizing the weighted number of tardy jobs.” Operations Research Letters 16(2): 79-86, 1994.
Jang, W. “Dynamic scheduling of stochastic jobs on a single machine.” European Journal of Operational Research 138(3): 518-530, 2002.
Jia, C. “Stochastic single machine scheduling with an exponentially distributed due date.” Operations Research Letters 28(5): 199-203, 2001.
Jolai, F. “Minimizing number of tardy jobs on a batch processing machine with incompatible job families.” European Journal of Operational Research 162(1): 184-190, 2005.
Kise, H. and T. Ibaraki. “On Balut's Algorithm and NP-Completeness for a Chance-Constrained Scheduling Problem.” Management Science 29(3): 384-388, 1983.
Monma, C. L. and C. N. Potts. “On the Complexity of Scheduling with Batch Setup Times.” Operations Research 37(5): 798-804, 1989.
Moore, J. M. “An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs.” Management Science 15(1): 102-109, 1968.
Perez, I. C., J. W. Fowler, W. M. Carlyle. “Minimizing total weighted tardiness on a single batch process machine with incompatible job families.” Computers & Operations Research 32(2): 327-341, 2005.
Pinedo, M. “Stochastic Scheduling with Release Dates and Due Dates.” Operations Research 31(3): 559-572, 1983.
Pinedo, M. Scheduling: Theory, Algorithms, and Systems. third ed. Springer Science Business Media. New York. 2008.
Potts, C. N. and M. Y. Kovalyov. “Scheduling with batching: A review.” European Journal of Operational Research 120(2): 228-249, 2000.
Rothkopf, M. H. “Scheduling with Random Service Times.” Management Science 12(9):707-713, 1966.
Sarin, S. C., E. Erel, G. Steiner. “Sequencing jobs on a single machine with a common due date and stochastic processing times.” European Journal of Operational Research 51(2): 188-198, 1991.
Seo, D. K., C. M. Klein, W. Jang. “Single machine stochastic scheduling to minimize the expected number of tardy jobs using mathematical programming models.” Computers & Industrial Engineering 48(2): 153-161, 2005.
Smith, W. E. “Various optimizers for single-stage production.” Naval Research Logistics Quarterly 3(1-2): 59-66, 1956.
Trietsch, D. and K. R. Baker. “Minimizing the number of tardy jobs with stochastically-ordered processing times.” Journal of Scheduling 11(1): 71-73, 2008.
Uzsoy, R. “Scheduling batch processing machines with incompatible job families.”International Journal of Production Research 33(10): 2685-2708, 1995.