关于重新排序问题的研究
|
摘要
排序就是在一定的约束条件下对若干个要加工的工件或任务在指定的机器上按时间进度进行分配和调度，使某一个或某一些指标达到最优。
重新排序问题是一种新型的排序模型。它有着重要的实际应用背景。生产部门根据自己的生产计划或是由客户提出的要求，在生产前一定时期内事先有一个作业方案，将已有的任务或订单按照某一规则安排好，使某一目标值最优。但是在即将开始生产之前或在生产过程中又有新的客户订单或任务到达。这时就要把新的任务和原有的还未加工的任务一起加工。为了不失信于对原客户的承诺或耽误原任务的完成，这就要求在原有的工件或任务的次序不至于打乱的过多的前提下，使得总的目标函数值达到最优。Hall和Potts(2004)在前人研究的基础上，系统地研究了重新排序问题。他们引入了序列错位(sequence disruption)和时间错位(time disruption)的概念，研究了在原来最优排序和任意排序的基础上重新排序，在原来排序的序列错位和时间错位不至于太大的情况下，使目标函数最优的问题。
多目标排序作为一种多目标决策，在解决经济、管理、工程、军事等领域出现的复杂问题中起着越来越重要的作用。例如，在一个工厂的生产过程中，生产决策者不但想要使工件的总完工时间最小以减少生产费用，还要尽量使误工工件的个数最少，以更好地满足顾客的要求。多目标排序包括字典序最优问题、Perato最优解问题和组合目标函数最优问题。
在线排序是指每个工件的信息在该工件到达之前是未知的。在工件的到达时间得到该工件的所有信息并允许对该工件进行加工；而且一旦决定工件的安排就不允许改变。而离线排序在安排所有工件之前便知道所有工件的信息。衡量一个在线排序算法最常用的指标是它的竞争度(competitiveness)，即把在线排序算法的结果与对相同工件运用离线排序算法得到的最优排序的结果进行比较。更确切的说，我们用竞争比(competitive ratio)ρ来衡量一个在线排序算法的性能。对于使目标函数为最小的在线排序问题，竞争比ρ定义为对问题的所有实例的比值C／C_0的上确界，其中C和C_0分别表示由这个在线排序算法得到的目标函数值和相应的离线排序的最优值。
本文的内容分四部分：第一部分研究了几种特殊情形的重新排序模型(第二章)。第二部分研究了一种新型重新排序模型(第三章)。第三部分研究了多目标的重新排序问题(第四章)。第四部分研究了在线的重新排序问题(第五章)。
在第二章中，研究了几种特殊情形的重新排序模型，其主要结果如下：对一些未解问题和强NP-困难问题，(1)给出了当工件的加工时间与工期相容或原始工件保持其相对顺序时，使得最大延迟和加工时间和为最小的多项式或拟多项式时间算法；(2)给出了当工件具有相同的加工时间或具有相同的工期时，使得误工和为最小的多项式或拟多项式时间算法；(3)给出了当工件的加工时间与权重反相容时，使得加权完工时间和为最小的多项式或拟多项式时间算法。
在第三章中，对于具有到达时间的最小化最大完工时间的重新排序问题，(1)给出了在最大序列错位约束下的最小化最大完工时间的重新排序问题的多项式时间算法；(2)给出了在总序列错位和约束下的最小化最大完工时间的重新排序问题的多项式时间算法；(3)证明了在最大时间错位或总时间错位约束下的最小化最大完工时间的重新排序问题是强NP-困难的。
在第四章中，对于多目标的重新排序问题，本文将错位量作为第二目标来考察，研究了四种错位量(D_(max)(π~*)，Δ_(max)(π~*)，∑D_j(π~*)，∑Δ_j(π~*))与传统的目标函数(如C_(max)，L_(max)，∑w_jC_j)的相互组合问题，给出了多目标排序中字典序最优问题、Perato最优解问题和线性组合目标函数最优问题的多项式时间算法或拟多项式时间算法。
在第五章中，主要研究了在线重新排序问题。即在原始工件已经按照某一规则排好，而新工件在原始工件的加工过程中是按时间顺序到达的。在此情形下，本文分别给出了在各种错位量约束下，目标函数为最小化最大延迟的竞争比为2的在线排序算法和最小化最大完工时间的竞争比为3／2的在线排序算法。
Scheduling is to allocate some jobs or tasks to some machines under a limited condition according to time order, and in order to optimize some objectives.
Rescheduling is one of significant modern scheduling models and it is motivated by important applications. The problem of rescheduling in the face of dynamically arriving orders is faced constantly by manufacturing companies. The manufacturing companies have been made their production schedules in earlier according to their planes or some customers' call, and schedule the jobs by some rule to optimize some objective. However it frequently happens that additional orders arrive after a schedule has been developed. These orders must then be integrated into the schedule so as to optimize some measure of system performance without causing undue disruption in the shop. Based on some researches, Hall and Potts (2004) studied the problem of rescheduling and introduced the conception of disruptions. They considered the rescheduling problem to minimize the maximum lateness and total completion time under a limit on the disruption constraints.
Multicriteria scheduling, as a way of multi-objective decision-making, plays an important role in solving complicated problems arising from economics, administration, engineering, etc.. For example, a factory administrator needs to arrange the jobs to be processed such that the total completion time is minimized firstly to reduce the processing cost and the tardy jobs are limited to a lowest level secondly, and to satisfy the clients. Multicriteria scheduling includes lexicographical optimization or hierarchical optimization, Pareto optimization and composite objective function optimization.
On-line scheduling is a modern scheduling model, in which the job information may not be known in advance. A job becomes available for processing at its arrival time, and its processing time only becomes known upon its arrival. Once the jobs have been scheduled, the states of the jobs cannot be changed. In the off-line scheduling, the information of all jobs has been completely known in advance. The performance of an on-line algorithm is described by its competitiveness, i.e. the ratio of the result of the on-line algorithm and the optimal value of the off-line situation for the same jobs. Exactly, for the problem of minimizing objective, the competitive ratioρof an on-line algorithm is defined as the supremum of the ratio of C and C_0, where C and C_0 are the objective of scheduling obtained by the on-line algorithm and an optimal off-line algorithm, respectively.
This paper includes four parts. In the first part, some spacial solvable cases of rescheduling models are considered (Chapter 2). In the second part, the new rescheduling models are studied (Chapter 3). In the third part, multi-criteria rescheduling models are discussed (Chapter 4). In the last part, on-line rescheduling problems are presented (Chapter 5).
In Chapter 2, the following results are developed. (1) The rescheduling problem to minimize the maximum lateness or the total completion time under a limit on the disruption constraints when d_j, p_j are compatible or the original jobs are fixed order are solvable in polynomial time or pseudo-polynomial time. (2) The rescheduling problem to minimize the total tardiness under a limit on the disruption constraints when p_j = p or d_j = d are solvable in polynomial time or pseudo-polynomial time. (3) The rescheduling problem for jobs on a single machine to minimize total weighted completion time under a limit on the maximum disruption when p_j and w_j of the jobs are anticompatible are solvable in polynomial time or pseudo-polynomial time.
In Chapter 3, the following results are developed. (1) The rescheduling problem for jobs on a single machine with release dates to minimize makespan under a limit on the maximum sequence disruption is solvable in polynomial time. (2) The rescheduling problem for jobs on a single machine with release dates to minimize makespan under a limit on the total sequence disruption can be solved in polynomial time. (3) The rescheduling problems for jobs on a single machine with release dates to minimize makespan under a limit on the maximum time disruption or the total time disruption are strongly NP-hard.
Chapter 4 studies the multicriteria rescheduling problems. In this parts, the disruptions of the original jobs are regarded as an objective in the same as classical objectives. The rescheduling problems of hierarchical optimization, Pareto optimization and linear composite objective function optimization between the classical scheduling cost (such as C_(max), L_(max),∑w_jC_j) of all the jobs and the degree of the disruptions (D_(max)(π~*),Δ_(max)(π~*),∑D_j(π~*),∑Δ_j(π~*)) are considered. For some problems, we provide a polynomial or pseudo-polynomial time algorithm.
Chapter 5 discusses the on-line rescheduling problems. In this parts, the original jobs have been arrived and sequenced by some rule, the new jobs arrive over time. For the online rescheduling problem to minimize the maximum lateness under a limit on the disruption constraints, a 2-competitive ratio algorithm is presented. For the online rescheduling problem to minimize makespan under a limit on the disruption constraints with release date, some |-competitive ratio algorithms are presented.
重新排序问题是一种新型的排序模型。它有着重要的实际应用背景。生产部门根据自己的生产计划或是由客户提出的要求，在生产前一定时期内事先有一个作业方案，将已有的任务或订单按照某一规则安排好，使某一目标值最优。但是在即将开始生产之前或在生产过程中又有新的客户订单或任务到达。这时就要把新的任务和原有的还未加工的任务一起加工。为了不失信于对原客户的承诺或耽误原任务的完成，这就要求在原有的工件或任务的次序不至于打乱的过多的前提下，使得总的目标函数值达到最优。Hall和Potts(2004)在前人研究的基础上，系统地研究了重新排序问题。他们引入了序列错位(sequence disruption)和时间错位(time disruption)的概念，研究了在原来最优排序和任意排序的基础上重新排序，在原来排序的序列错位和时间错位不至于太大的情况下，使目标函数最优的问题。
多目标排序作为一种多目标决策，在解决经济、管理、工程、军事等领域出现的复杂问题中起着越来越重要的作用。例如，在一个工厂的生产过程中，生产决策者不但想要使工件的总完工时间最小以减少生产费用，还要尽量使误工工件的个数最少，以更好地满足顾客的要求。多目标排序包括字典序最优问题、Perato最优解问题和组合目标函数最优问题。
在线排序是指每个工件的信息在该工件到达之前是未知的。在工件的到达时间得到该工件的所有信息并允许对该工件进行加工；而且一旦决定工件的安排就不允许改变。而离线排序在安排所有工件之前便知道所有工件的信息。衡量一个在线排序算法最常用的指标是它的竞争度(competitiveness)，即把在线排序算法的结果与对相同工件运用离线排序算法得到的最优排序的结果进行比较。更确切的说，我们用竞争比(competitive ratio)ρ来衡量一个在线排序算法的性能。对于使目标函数为最小的在线排序问题，竞争比ρ定义为对问题的所有实例的比值C／C_0的上确界，其中C和C_0分别表示由这个在线排序算法得到的目标函数值和相应的离线排序的最优值。
本文的内容分四部分：第一部分研究了几种特殊情形的重新排序模型(第二章)。第二部分研究了一种新型重新排序模型(第三章)。第三部分研究了多目标的重新排序问题(第四章)。第四部分研究了在线的重新排序问题(第五章)。
在第二章中，研究了几种特殊情形的重新排序模型，其主要结果如下：对一些未解问题和强NP-困难问题，(1)给出了当工件的加工时间与工期相容或原始工件保持其相对顺序时，使得最大延迟和加工时间和为最小的多项式或拟多项式时间算法；(2)给出了当工件具有相同的加工时间或具有相同的工期时，使得误工和为最小的多项式或拟多项式时间算法；(3)给出了当工件的加工时间与权重反相容时，使得加权完工时间和为最小的多项式或拟多项式时间算法。
在第三章中，对于具有到达时间的最小化最大完工时间的重新排序问题，(1)给出了在最大序列错位约束下的最小化最大完工时间的重新排序问题的多项式时间算法；(2)给出了在总序列错位和约束下的最小化最大完工时间的重新排序问题的多项式时间算法；(3)证明了在最大时间错位或总时间错位约束下的最小化最大完工时间的重新排序问题是强NP-困难的。
在第四章中，对于多目标的重新排序问题，本文将错位量作为第二目标来考察，研究了四种错位量(D_(max)(π~*)，Δ_(max)(π~*)，∑D_j(π~*)，∑Δ_j(π~*))与传统的目标函数(如C_(max)，L_(max)，∑w_jC_j)的相互组合问题，给出了多目标排序中字典序最优问题、Perato最优解问题和线性组合目标函数最优问题的多项式时间算法或拟多项式时间算法。
在第五章中，主要研究了在线重新排序问题。即在原始工件已经按照某一规则排好，而新工件在原始工件的加工过程中是按时间顺序到达的。在此情形下，本文分别给出了在各种错位量约束下，目标函数为最小化最大延迟的竞争比为2的在线排序算法和最小化最大完工时间的竞争比为3／2的在线排序算法。
Scheduling is to allocate some jobs or tasks to some machines under a limited condition according to time order, and in order to optimize some objectives.
Rescheduling is one of significant modern scheduling models and it is motivated by important applications. The problem of rescheduling in the face of dynamically arriving orders is faced constantly by manufacturing companies. The manufacturing companies have been made their production schedules in earlier according to their planes or some customers' call, and schedule the jobs by some rule to optimize some objective. However it frequently happens that additional orders arrive after a schedule has been developed. These orders must then be integrated into the schedule so as to optimize some measure of system performance without causing undue disruption in the shop. Based on some researches, Hall and Potts (2004) studied the problem of rescheduling and introduced the conception of disruptions. They considered the rescheduling problem to minimize the maximum lateness and total completion time under a limit on the disruption constraints.
Multicriteria scheduling, as a way of multi-objective decision-making, plays an important role in solving complicated problems arising from economics, administration, engineering, etc.. For example, a factory administrator needs to arrange the jobs to be processed such that the total completion time is minimized firstly to reduce the processing cost and the tardy jobs are limited to a lowest level secondly, and to satisfy the clients. Multicriteria scheduling includes lexicographical optimization or hierarchical optimization, Pareto optimization and composite objective function optimization.
On-line scheduling is a modern scheduling model, in which the job information may not be known in advance. A job becomes available for processing at its arrival time, and its processing time only becomes known upon its arrival. Once the jobs have been scheduled, the states of the jobs cannot be changed. In the off-line scheduling, the information of all jobs has been completely known in advance. The performance of an on-line algorithm is described by its competitiveness, i.e. the ratio of the result of the on-line algorithm and the optimal value of the off-line situation for the same jobs. Exactly, for the problem of minimizing objective, the competitive ratioρof an on-line algorithm is defined as the supremum of the ratio of C and C_0, where C and C_0 are the objective of scheduling obtained by the on-line algorithm and an optimal off-line algorithm, respectively.
This paper includes four parts. In the first part, some spacial solvable cases of rescheduling models are considered (Chapter 2). In the second part, the new rescheduling models are studied (Chapter 3). In the third part, multi-criteria rescheduling models are discussed (Chapter 4). In the last part, on-line rescheduling problems are presented (Chapter 5).
In Chapter 2, the following results are developed. (1) The rescheduling problem to minimize the maximum lateness or the total completion time under a limit on the disruption constraints when d_j, p_j are compatible or the original jobs are fixed order are solvable in polynomial time or pseudo-polynomial time. (2) The rescheduling problem to minimize the total tardiness under a limit on the disruption constraints when p_j = p or d_j = d are solvable in polynomial time or pseudo-polynomial time. (3) The rescheduling problem for jobs on a single machine to minimize total weighted completion time under a limit on the maximum disruption when p_j and w_j of the jobs are anticompatible are solvable in polynomial time or pseudo-polynomial time.
In Chapter 3, the following results are developed. (1) The rescheduling problem for jobs on a single machine with release dates to minimize makespan under a limit on the maximum sequence disruption is solvable in polynomial time. (2) The rescheduling problem for jobs on a single machine with release dates to minimize makespan under a limit on the total sequence disruption can be solved in polynomial time. (3) The rescheduling problems for jobs on a single machine with release dates to minimize makespan under a limit on the maximum time disruption or the total time disruption are strongly NP-hard.
Chapter 4 studies the multicriteria rescheduling problems. In this parts, the disruptions of the original jobs are regarded as an objective in the same as classical objectives. The rescheduling problems of hierarchical optimization, Pareto optimization and linear composite objective function optimization between the classical scheduling cost (such as C_(max), L_(max),∑w_jC_j) of all the jobs and the degree of the disruptions (D_(max)(π~*),Δ_(max)(π~*),∑D_j(π~*),∑Δ_j(π~*)) are considered. For some problems, we provide a polynomial or pseudo-polynomial time algorithm.
Chapter 5 discusses the on-line rescheduling problems. In this parts, the original jobs have been arrived and sequenced by some rule, the new jobs arrive over time. For the online rescheduling problem to minimize the maximum lateness under a limit on the disruption constraints, a 2-competitive ratio algorithm is presented. For the online rescheduling problem to minimize makespan under a limit on the disruption constraints with release date, some |-competitive ratio algorithms are presented.
引文
[1] Anderson, E. J. and Potts, C. N. Onlinf scheduling of a single machine to minimize total weighted completion time, Mathematics of Operations Research, 3 (2004), 286-697.
[2] Agnetis,A., Mirchandani,P.B., Pacciarelli,D. and Pacifici,A., Scheduling problems with two competing agents, Operations Research, 52 (2004), 229-242.
[3] Ausiello,G. and Paschos,V.Th., Reductions, completeness and the hardness of approximability, European Journal of Operational Research, 172 (2006), 719-739.
[4] Azar,Y. and Epstein,L., On-line scheduling with precedence constraints, Discrete Applied Mathematics, 119(2002), 169-180.
[5] Baker,K.R. and Smith,J.C., A multiple-criterion model for machine scheduling, Journal of Scheduling, 6 (2003), 7-16.
[6] Baker,K.R., Scheduling the production of components at a common facility, IIE Transactions, 20(1988), 32-35.
[7] Baker,K.R. and Scudder,G.D., Sequencing with earliness and tardiness penalties: a review, Operations Research, 38(1990), 22-36.
[8] Baptiste,P., Batching identical jobs, Mathematical Methods of Operations Research, 52(2000), 355-367.
[9] Bean,J.C., Birge,J.R., Mittenthal,J. and Noon,C.E., Matchup scheduling with multiple resources,release dates and disruptions, Operations Research, 39(1991), 470-483.
[10] Bhatia,R., Khuller,S. and Naor,J., The loading time scheduling problem, Journal of Algorithms, 36(2000), 1-33.
[11] Blazewicz,J., Ecrer,K. and Weglarz,J., Scheduling in computer and manufactureing systems, Springer Verlag, Berlin, 1993.
[12] Blazewicz,J. and Kovalyov,M.Y., The complexity of two group scheduling problems, Journal of Schduling, 5(2002), 477-485.
[13] Brucker,P., Scheduling Algorithms, Springer-Verlag, Berlin, 2001.
[14] Brucker,P., Garey, M. R. and Johnson, D. S., Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness, Mathematics of Operations Research, 2(1977), 275-284.
[15] Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M. Y., Potts, C. N., Tautenhahn, T. and van de Velde, S. L., Scheduling a hatching machine, Journal of Scheduling, 1(1998), 31-54.
[16] Brucker, P. and Knust, S., Complexity results for scheduling problems, http://www.mathematik.uni-osnabrueck.de/research/OR/class/, 2003.
[17] Bruno, J. and Downey, P., Complexity of task sequencing with deadlines, set-up times and changeover costs, SIAM Journal on Computing, 7(1978), 393-404.
[18] Chang, Y. C. and Lee, C. Y., Machine scheduling with job delivery coordination, European Journal of Operational Research, 158(2004), 470-487.
[19] Chandru, V., Lee, C. Y. and Uzsoy, R., Minimizing total completion time on batch processing machines, Int. J. Prod. Res., 31(1993), 2097-2122.
[20] Chekuri, C., Motwani, R., Nataralan, B. and Stein, C., Approximation techniques for average completion time scheduling, SIAM Journal of Computing, 1(2001), 146-166.
[21] Chen, B., Deng, X. T. and Zang, W. A., On-line scheduing a batch processing system to minimize total weighted job completion time, Journal of Combinatorial Optimization, 8(2004), 85-95.
[22] Chen, B., Potts, C. N. and Woeginger, G. J., A review of machine scheduling: complexity, algorithms and approximability, in: D. Z. Du and P. M. Pardalos (eds.), Handbook of Combinatorial Optimization, Kluwer Academic Publishers, (1998), 21-169.
[23] Chen, B. and Vestjens, A. P. A., Scheduling on identical machines: How good is LPT in an on-line setting?, Operations Researth Letters, 21(1997), 165-169.
[24] Chen, B., Vliet, A. V. and Woeginger, G. J., An optimal algorithm for preemptive online scheduling, Operations Researth Letters, 18(1995), 127-131.
[25] Chen, C. L. and Bulfin, R. L., Complexity of single machine, multi-criteria scheduling problems, European Journal of Operational Research, 70(1993), 115-125.
[26] Cheng, T., Optimal common due date with limited completion time deviation, Computers and Operations Research, 15(1988), 91-96.
[27] Cheng, T. C. E., Ng, C. T. and Yuan, J. J., The single machine hatching problem with family setup times to minimize maximum lateness is strongle NP-hard, Journal of Scheduling, 6(2003), 483-490.
[28] Cheng, T. C. E., Ng, C. T., Yuan, J. J. and Liu, Z. H., Single machine parallel batch scheduling subject to precedence constraints, Naval Reasearch Logistics, 51(2004), 949-958.
[29] Cheng, T. C. E., Liu, Z. H. and Yu, W. C., Scheduling jobs with release dates and deadlines on a batch processing machine, IIE Transactions, 33(2001), 685-690.
[30] Church, L. K. and Uzsoy, R., Analysis of periodic and event-driven rescheduling policies in dynamic shops, Int. J. Compt. Integrated Manufacturing, 5(1992), 153-163.
[31] Dang, C. Y. and Kang, L. Y., Batch-processing scheduling with setup times, Journal of Combinatorial Optimization, 8(2004), 137-146.
[32] Daniels, R. L. and Kouvelis, P., Robust scheduling to hedge against processing time uncertainty in single-stage production, Management Science, 41(1995), 363-376.
[33] Deng, X., Feng, H. D., Li, G. J. and Shi, B. Y., A PTAS for semiconductor burn-in scheduling, Journal of Combinatorial Optimization, 9(2005), 5-17.
[34] Deng, X. and Zhang, Y. Z., Minimizing mean response time for batch processing systems, Lecture notes in Computer Science, 1627(1999), 231-240.
[35] Dobson, G., Karmarkar, U. S. and Rummel, J. L., Batching to minimize flow times on one machine, Management Science, 33(1987), 784-799.
[36] Du, J. and Leung, J. Y. T., Minimizing total tardiness on one machine is NP-hard, Mathematics of Operations Research, 15(1990), 483-493.
[37] Engels, D. W., Karger, D. R., Kolliopoulos, S. G., Sengupta, S., Urea R. N. and Wein, J., Techniques for scheduling with rejection, Journal of Algorithms, 49(2003), 175- 191.
[38] Epstein, L, A note on on-line scheduling with precedence constraints on identical machines, Information Processing Letters, 76(2000), 149-153.
[39] Epstein, L. and Stee, R. V., Lower bounds for on-line single-machine scheduling, Theoretical Computer Science, 299(2003), 439-450.
[40] Garey, M. R. and Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979.
[41] Garey, M. R., Tarjan, R. E. and Wilfong, G. T., One-processor scheduling with symmetric earliness and tardiness penalties, Mathematics of Operations Research, 13(1988), 330-338.
[42] Ghazvini, F. J. and Dupont, L., Minimizing mean flow times criteria on a single batch processing machine with non-identical jobs sizes, Int. J. Production Economics, 55(1998), 273-280.
[43] Goemans, M. X., Queyranne, M., Schulz, A. S., Skutella, M. and Wang, Y. G., Single machine scheduling with release dates, SIAM Journal of Discrete Mathematics, 2(2002), 165-192.
[44] Graham, R. L., Lawler, E. L., Lenstra, J. K. and Rinnooy Kan, A. H. G., Optimization and approximation in deterministic machine scheduling: A survey, Annals of Discrete Mathematics, 5(1979), 287-326.
[45] Gupta, J. N. D., Single facility scheduling with multiple job classes, European Journal of Operational Reaearch, 33(1988), 42-45.
[46] Graham, R. L., Lawler, E. L., Lenstra, J. K. and Rinnooy Kan, A. H. G., Optomization and approximation in deterministic machine scheduling: A survey, Annals of Discrete Mathematics, 5 (1979), 287-326.
[47] Hall, N. G. and Posner, M. E., Earliness-tardiness scheduling problems, I: weighted deviation of completion times about a common due date, Operations Reaearch, 39(1991), 836-846.
[48] Hall, N. G. and Posner, M. E., Sensitivity analysis for scheduling problems, Journal of Scheduling, 7(2004), 49-83.
[49] Hall, N. G. and Potts, C. N., Rescheduling for new orders, Operations Research, 52 (2004), 440-453.
[50] Hall, N. G. and Potts, C. N., The coordination of scheduling and batch deliveries, Annals of Operations Research, 135 (2005), 41-64.
[51] Hall, L. A., Schulz, A. S., Shmoys, D. B. and Wein, J., Scheduling to minimize average completion time: off-line and on-line approximation algorithms mathematics of Operations Research, 3 (1997), 513-544.
[52] Hariri, A. M. A. and Potts, C. N., Single machine scheduling with batch set-up times to minimize maximum lateness, Annals of Operations Reaearch, 70 (1997), 75-92.
[53] Hochbaum, D. S., Approximation algorithms for NP-hard problems, PWS Publishing Company. (1998).
[54] Hochbaum, D. S. and Landy, D., Scheduling semiconductor burn-in operations to minimize total flowtime, Operations Reaearch, 6 (1994), 874-885.
[55] Hoogeveen, H., Multicriteria scheduling, European Journal of Operational Reaearch, 167(2005), 592-623.
[56] Hoogeveen, J. A., Potts, C. N. and Woeginger, G. J., On-line scheduling on a singlemachine: maximizing the number of early jobs, Operation Research Letters, 27(2000), 193-197.
[57] Hoogeveen, H. and van de velde, S. L., Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time, Operation Research Letters, 17 (1995), 205-208.
[58] Hoogeveen, J. A. and Vestjens, A. P. A., Optimal on-line algorithms for single-machine scheduling, Proceedings of the 5th IPCO conference, (1996), 404-412.
[59] Hoogeveen, J. A. and Vestjens, A. P. A., A best possible deterministic on-line algorithms for minimizing maximum delivery time on a single-machine, SIAM Journal of Discrete Mathematics, 1(2000), 56-63.
[60] Hoogeveen, H. and van de velde, S. L., Scheduling with target start times, European Journal of Operational Reaearch, 129 (2001), 87-94.
[61] Jain, A. K. and Elmaraghy, H. A., production scheduling/rescheduling in flexible manufacturing, International Journal of Production Research, 35(1997), 281-309.
[62] Kanet, J. J., Minimizing the average deviation of job completion times about a common due date, Naval Research Logistic Quarter/y, 28(1981), 643-651.
[63] Koulamas, C. and Kyparisis, G. J., Single machine scheduling with release times, deadlines and tardiness objectives, European Journal of Operational Research, 133 (2001), 447-453.
[64] Lauff, V. and Werner, F., On the complexity and some properties of multi-stage scheduling problems with earliness and tardiness penalties, Computers and Operations Research, 31 (2004), 317-345.
[65] Lawler, E. L., A "pseudopolynomial" algorithm for sequencing jobs to minimize total tardiness, Annals of Discrete Mathmatics, 1 (1977), 331-342.
[66] Lawler, E. L., Combinatorial Optimization: Networks and Matroids, Holt, Rinehart & Winston, New York, 1976.
[67] Lawler, E. L., Optimal sequencing of a single machine subject to precedence constraints, Management Science, 19 (1973), 544-546.
[68] Lawler, E. L., Sequencing jobs to minimize total weighted completion time subject to precedence constraints, Annals of Discrete Mathematics, 2 (1978), 75-90.
[69] Lee, C. Y., Uzsoy, R. and Martin-Vega, L. A., Efficient algorithms for scheduling semiconductor burn-in operations, Operations Research, 40 (1992), 764-775.
[70] Lee, C. Y. and Vairaktarakis, G. L., Complexity of single machine hierarchical scheduling: A survey, In: Complexity in Numerical Optimization (P. M. Pardalos edits), World Scientific Publishing Company, New Jersey, (1993), 269-298.
[71] Lenstra, J. K., Rinnooy Kan, A. H. G. and Brucker, P., Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1 (1977), 343-362.
[72] Li, R., Shyu, Y. and Adiga, S., A heuristic rescheduling algorithm for computer-based production scheduling system, International Journal of Production Research, 31 (1993), 1815-1826.
[73] Li, S. G., Li, G. J., Wang, X. L. and Liu, Q. M., Minimizing makespan on a single batching machine with release times and non-identical job sizes, Operations Research Letters, 33 (2005), 157-164.
[74] Lin, B. M. T., The strong NP-hardness of two-stage flowshop scheduling with a common second-stage machine, Computers & Operations Research, 26 (1999), 695-698.
[75] Liu, Z. H. and Cheng, T. C. E., Approximation schemes for minimizing total (weighted) completion time with release dates on a batch machine, Theoretical Computer Science, 347 (2005), 288-298.
[76] Liu, Z. H. and Yu, W. C., Scheduling one batch processor subject to job release dates, Discrete Applied Mathematics, 105 (2000), 129-136.
[77] Liu, Z. H., Yuan, J. J. and Cheng, T. C. E., On scheduling an unbounded batch machine, Operations Research Letters, 31 (2003), 42-48.
[78] Mason, A. J. and Anderson, E. J., Minimizing flow time on a single machine with job classes and setup times, Naval Research Logistics, 38 (1991), 333-350.
[79] Mehta, S. V. and Uzsoy, R., Prodictable scheduling of a single machine bubject to breakdowns, Internat. J. Comput. Integrated Manufacturing, 12 (1999), 15-38.
[80] Moukrim, A., Optimal scheduling on parallel machines for a new order class, Operations Research Letters, 24 (1999), 91-95.
[81] Naroska, E., Schwiegelshohn, U., On an on-line scheduling problem for Parallel jobs, Theoretical Computer Science, 81 (2002), 297-304.
[82] Nelson, R. T., Sarin, R. K. and Daniels, R. L., Scheduling with multiple performance measures: The one-machine case, Management Science, 4 (1986), 464-479.
[83] Ng, C. T., Cheng, T. C. E. and Yuan, J. J., A note on the single machine serial batching scheduling problem to minimize maximum lateness with precedence constraints, Operation Research Letters, 30 (2002), 66-68.
[84] Ng, C. T., Cheng, T. C. E. and Yuan, J. J., Strong NP-hardness of the single machine multi-opteration jobs total completion time scheduling problem, Information Processing Letters, 82 (2002), 187-191.
[85] Ng, C. T., Cheng, T. C. E., Yuan, J. J. and Liu, Z. H., On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times, Operation Research Letters, 31(2003), 323-326.
[86] Naroska, E., Schwiegelshohn, U., On an on-line scheduling problem for Parallel jobs, Theoretical Computer Science, 81 (2002), 297-304.
[87] O'Donovan, R., Uzsoy, R. and Mckay, K. N., Predictable scheduling of a single machine with breakdown and sensitive jobs, Int. J. Production Research, 37 (1999), 4217-4233.
[88] Panwalkar, S. S., Smith, M. L. and Seidmann, A., Common due date assignment to minimize total penalty for the one machine scheduling problem of single machine, Operational Research, 30 (1982), 391-399.
[89] Papadimitriou, C. H. and Steiglitz, K., Combinatorial Optimization: Algorithms and Cornplexity, Prentice-Hall, Englewood Cliffs, NJ, 1982.
[90] Phillips, C., Stein, C. and Wein, J., Minimizing average completion time in the presence of release dates, Mathematical Programming, 82 (1998), 199-223.
[91] Potts, C. N. and Kovalyov, M. Y., Scheduling with batching: a review, European Journal of Operational Research, 120 (2000), 228-249.
[92] Pinedo, M., Scheduling: Theory, Algorithms and Systems, Prentice-Hall, Englewood Cliffs, NJ, 1995.
[93] Raman, N., Talbot, F. B. and Rachamadugu, R. V., Due date based scheduling in a general flexible manufacturing system, Journal of Oper. Management, 8 (1989), 115-132.
[94] Raghavachari, M., A V-shape property of optimal schedule of jobs about a common due date, European Journal of Operational Research, 23 (1986), 401-402.
[95] Santos, C. A. and Magazing, M., Batching in single operation manufacturing systems, Operations Research Letters, 4 (1985), 99-103.
[96] Schutten, J. M. J., van de Velde, S. L. and Zijm, W. H. M., Single machine scheduling with release dates, due dates and family setup times, Managernent Science, 42 (1996), 1165-1174.
[97] Schuurman, P. and Woeginger, G. J., Polynomial time approximation algorithms for machine scheduling: ten open problems, Journal of Scheduling, 2 (1999), 203-213.
[98] Shallcross, D., A polynomial algorithm for a one machine batching problem, Operations Research Letters, 11(1992), 213-218.
[99] Simons, B., Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines, SIAM Journal on Computing, 12(2) (1983), 294-299.
[100] Skutella, M. and Woeginger, G. J., A PTAS for minimizing the total weighted completion time on identical parallel machines, Mathematics of Operations Research, 1 (2000), 63-75.
[101] Scharbrodt, M., Steger, A. and Weisser, H., Approximability of scheduling with fixed jobs, Journal of scheduling, 3(1999), 267-284.
[102] T'kindt, V. and Billaut, J. C., Multicriteria Scheduling: Theory, Models and Algorithms, Springer, Berlin, 2002.
[103] 唐恒永，赵传立，排序引论，科学出版社，2002．
[104] 唐国春，张峰，罗守成，刘丽丽，现代排序论，上海科学普及出版社，2003．
[105] Ullman, J. D., NP-complete scheduling problems, Journal of Computer and System Sciences, 10 (1975), 384-393.
[106] Unal, A. T., Uzsoy, R. and Kiran, A. S., Rescheduling on a single machine with parttype depend setup times and deadlines, Annals of Operations Research, 70 (1997), 93-113.
[107] Uzsoy, R., Scheduling batch processing machines with incompatible job families, Int. J. Prod. Res., 33 (1995), 2685-2708.
[108] Van Wassenhove, L. N. and Gelders, L. F., Solving a bicriteria scheduling problem, European Journal of Operational Research, 4 (1980), 42-48.
[109] Webster, S. T., The complexity of scheduling job families about a common due date, Operations Research Letters, 20 (1997), 65-74.
[110] Webster, S. T. and Baker, K. R., Scheduling groups of jobs on a single machine, Operations Research, 43 (1995), 692-703.
[111] Williams, D. and Wirth, A., A new heuristic for a single machine scheduling problem with set-up times, Journal of the Operational Research Society, 47 (1996), 175-180.
[112] Wu, S. D., Storer, R. H. and Chang, P. C., A rescheduling procedure for manufacturing systems under random disruptions. G. Fandel, T. Gulledge, A. Jone, eds. New Directions for Operations Research in Manufacturing. Springer, Berlin, Germany, (1992), 292-308.
[113] Wu, S. D., Storer, R. H. and Chang, P. C., One-machine rescheduling heuristics with efficiency and stability as criteria, Comput. Oper. Res., 20 (1993), 1-14.
[114] Yuan, J. J. and Lin, Y. X., Single machine preemptive scheduling with fixed jobs to minimize tardiness related criteria, European Journal of Operational Research, 164 (2005), 851-855.
[115] 原晋江，林诒勋，关于具有主次指标的单机排序的注记，高校应用数学学报，第11卷第2期(1996)，207-212．
[116] Yuan, J. J., Liu, Z. H., Ng, C. T. and Cheng, T. C. E., The single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan, Theoretical Computer Science, 320 (2004), 199-212.
[117] Yellig, E. J. and Mackulak, G. T., Robust deterministic scheduling in stochastic environments: the method of capacity hedge points, International Journal of Production Research, 35(1997), 369-379.
[118] 越民义，组合优化导论，浙江科学技术出版社，2001．
[119] Zdrzalka, S., Analysis of approximation algorithms for single-machine scheduling with delivery times and sequence independent batch setup times, European Journal of Operational Research, 80 (1995), 371-380.
[120] Zhang,G.C, Cai,X.Q., Lee,C.Y. and Wong,C.K., Minimizing makespan on a single batch processing machine with nonidentical job sizes, Naval Research Logistics, 48 (2001), 226-240.
[121] Zhang,G.C, Cai,X.Q. and Wong,C.K., On-line algorithms for minimizing makespan on batch processing machines, Naval Research Logistics, 48 (2001), 241-258.
[2] Agnetis,A., Mirchandani,P.B., Pacciarelli,D. and Pacifici,A., Scheduling problems with two competing agents, Operations Research, 52 (2004), 229-242.
[3] Ausiello,G. and Paschos,V.Th., Reductions, completeness and the hardness of approximability, European Journal of Operational Research, 172 (2006), 719-739.
[4] Azar,Y. and Epstein,L., On-line scheduling with precedence constraints, Discrete Applied Mathematics, 119(2002), 169-180.
[5] Baker,K.R. and Smith,J.C., A multiple-criterion model for machine scheduling, Journal of Scheduling, 6 (2003), 7-16.
[6] Baker,K.R., Scheduling the production of components at a common facility, IIE Transactions, 20(1988), 32-35.
[7] Baker,K.R. and Scudder,G.D., Sequencing with earliness and tardiness penalties: a review, Operations Research, 38(1990), 22-36.
[8] Baptiste,P., Batching identical jobs, Mathematical Methods of Operations Research, 52(2000), 355-367.
[9] Bean,J.C., Birge,J.R., Mittenthal,J. and Noon,C.E., Matchup scheduling with multiple resources,release dates and disruptions, Operations Research, 39(1991), 470-483.
[10] Bhatia,R., Khuller,S. and Naor,J., The loading time scheduling problem, Journal of Algorithms, 36(2000), 1-33.
[11] Blazewicz,J., Ecrer,K. and Weglarz,J., Scheduling in computer and manufactureing systems, Springer Verlag, Berlin, 1993.
[12] Blazewicz,J. and Kovalyov,M.Y., The complexity of two group scheduling problems, Journal of Schduling, 5(2002), 477-485.
[13] Brucker,P., Scheduling Algorithms, Springer-Verlag, Berlin, 2001.
[14] Brucker,P., Garey, M. R. and Johnson, D. S., Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness, Mathematics of Operations Research, 2(1977), 275-284.
[15] Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M. Y., Potts, C. N., Tautenhahn, T. and van de Velde, S. L., Scheduling a hatching machine, Journal of Scheduling, 1(1998), 31-54.
[16] Brucker, P. and Knust, S., Complexity results for scheduling problems, http://www.mathematik.uni-osnabrueck.de/research/OR/class/, 2003.
[17] Bruno, J. and Downey, P., Complexity of task sequencing with deadlines, set-up times and changeover costs, SIAM Journal on Computing, 7(1978), 393-404.
[18] Chang, Y. C. and Lee, C. Y., Machine scheduling with job delivery coordination, European Journal of Operational Research, 158(2004), 470-487.
[19] Chandru, V., Lee, C. Y. and Uzsoy, R., Minimizing total completion time on batch processing machines, Int. J. Prod. Res., 31(1993), 2097-2122.
[20] Chekuri, C., Motwani, R., Nataralan, B. and Stein, C., Approximation techniques for average completion time scheduling, SIAM Journal of Computing, 1(2001), 146-166.
[21] Chen, B., Deng, X. T. and Zang, W. A., On-line scheduing a batch processing system to minimize total weighted job completion time, Journal of Combinatorial Optimization, 8(2004), 85-95.
[22] Chen, B., Potts, C. N. and Woeginger, G. J., A review of machine scheduling: complexity, algorithms and approximability, in: D. Z. Du and P. M. Pardalos (eds.), Handbook of Combinatorial Optimization, Kluwer Academic Publishers, (1998), 21-169.
[23] Chen, B. and Vestjens, A. P. A., Scheduling on identical machines: How good is LPT in an on-line setting?, Operations Researth Letters, 21(1997), 165-169.
[24] Chen, B., Vliet, A. V. and Woeginger, G. J., An optimal algorithm for preemptive online scheduling, Operations Researth Letters, 18(1995), 127-131.
[25] Chen, C. L. and Bulfin, R. L., Complexity of single machine, multi-criteria scheduling problems, European Journal of Operational Research, 70(1993), 115-125.
[26] Cheng, T., Optimal common due date with limited completion time deviation, Computers and Operations Research, 15(1988), 91-96.
[27] Cheng, T. C. E., Ng, C. T. and Yuan, J. J., The single machine hatching problem with family setup times to minimize maximum lateness is strongle NP-hard, Journal of Scheduling, 6(2003), 483-490.
[28] Cheng, T. C. E., Ng, C. T., Yuan, J. J. and Liu, Z. H., Single machine parallel batch scheduling subject to precedence constraints, Naval Reasearch Logistics, 51(2004), 949-958.
[29] Cheng, T. C. E., Liu, Z. H. and Yu, W. C., Scheduling jobs with release dates and deadlines on a batch processing machine, IIE Transactions, 33(2001), 685-690.
[30] Church, L. K. and Uzsoy, R., Analysis of periodic and event-driven rescheduling policies in dynamic shops, Int. J. Compt. Integrated Manufacturing, 5(1992), 153-163.
[31] Dang, C. Y. and Kang, L. Y., Batch-processing scheduling with setup times, Journal of Combinatorial Optimization, 8(2004), 137-146.
[32] Daniels, R. L. and Kouvelis, P., Robust scheduling to hedge against processing time uncertainty in single-stage production, Management Science, 41(1995), 363-376.
[33] Deng, X., Feng, H. D., Li, G. J. and Shi, B. Y., A PTAS for semiconductor burn-in scheduling, Journal of Combinatorial Optimization, 9(2005), 5-17.
[34] Deng, X. and Zhang, Y. Z., Minimizing mean response time for batch processing systems, Lecture notes in Computer Science, 1627(1999), 231-240.
[35] Dobson, G., Karmarkar, U. S. and Rummel, J. L., Batching to minimize flow times on one machine, Management Science, 33(1987), 784-799.
[36] Du, J. and Leung, J. Y. T., Minimizing total tardiness on one machine is NP-hard, Mathematics of Operations Research, 15(1990), 483-493.
[37] Engels, D. W., Karger, D. R., Kolliopoulos, S. G., Sengupta, S., Urea R. N. and Wein, J., Techniques for scheduling with rejection, Journal of Algorithms, 49(2003), 175- 191.
[38] Epstein, L, A note on on-line scheduling with precedence constraints on identical machines, Information Processing Letters, 76(2000), 149-153.
[39] Epstein, L. and Stee, R. V., Lower bounds for on-line single-machine scheduling, Theoretical Computer Science, 299(2003), 439-450.
[40] Garey, M. R. and Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1979.
[41] Garey, M. R., Tarjan, R. E. and Wilfong, G. T., One-processor scheduling with symmetric earliness and tardiness penalties, Mathematics of Operations Research, 13(1988), 330-338.
[42] Ghazvini, F. J. and Dupont, L., Minimizing mean flow times criteria on a single batch processing machine with non-identical jobs sizes, Int. J. Production Economics, 55(1998), 273-280.
[43] Goemans, M. X., Queyranne, M., Schulz, A. S., Skutella, M. and Wang, Y. G., Single machine scheduling with release dates, SIAM Journal of Discrete Mathematics, 2(2002), 165-192.
[44] Graham, R. L., Lawler, E. L., Lenstra, J. K. and Rinnooy Kan, A. H. G., Optimization and approximation in deterministic machine scheduling: A survey, Annals of Discrete Mathematics, 5(1979), 287-326.
[45] Gupta, J. N. D., Single facility scheduling with multiple job classes, European Journal of Operational Reaearch, 33(1988), 42-45.
[46] Graham, R. L., Lawler, E. L., Lenstra, J. K. and Rinnooy Kan, A. H. G., Optomization and approximation in deterministic machine scheduling: A survey, Annals of Discrete Mathematics, 5 (1979), 287-326.
[47] Hall, N. G. and Posner, M. E., Earliness-tardiness scheduling problems, I: weighted deviation of completion times about a common due date, Operations Reaearch, 39(1991), 836-846.
[48] Hall, N. G. and Posner, M. E., Sensitivity analysis for scheduling problems, Journal of Scheduling, 7(2004), 49-83.
[49] Hall, N. G. and Potts, C. N., Rescheduling for new orders, Operations Research, 52 (2004), 440-453.
[50] Hall, N. G. and Potts, C. N., The coordination of scheduling and batch deliveries, Annals of Operations Research, 135 (2005), 41-64.
[51] Hall, L. A., Schulz, A. S., Shmoys, D. B. and Wein, J., Scheduling to minimize average completion time: off-line and on-line approximation algorithms mathematics of Operations Research, 3 (1997), 513-544.
[52] Hariri, A. M. A. and Potts, C. N., Single machine scheduling with batch set-up times to minimize maximum lateness, Annals of Operations Reaearch, 70 (1997), 75-92.
[53] Hochbaum, D. S., Approximation algorithms for NP-hard problems, PWS Publishing Company. (1998).
[54] Hochbaum, D. S. and Landy, D., Scheduling semiconductor burn-in operations to minimize total flowtime, Operations Reaearch, 6 (1994), 874-885.
[55] Hoogeveen, H., Multicriteria scheduling, European Journal of Operational Reaearch, 167(2005), 592-623.
[56] Hoogeveen, J. A., Potts, C. N. and Woeginger, G. J., On-line scheduling on a singlemachine: maximizing the number of early jobs, Operation Research Letters, 27(2000), 193-197.
[57] Hoogeveen, H. and van de velde, S. L., Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time, Operation Research Letters, 17 (1995), 205-208.
[58] Hoogeveen, J. A. and Vestjens, A. P. A., Optimal on-line algorithms for single-machine scheduling, Proceedings of the 5th IPCO conference, (1996), 404-412.
[59] Hoogeveen, J. A. and Vestjens, A. P. A., A best possible deterministic on-line algorithms for minimizing maximum delivery time on a single-machine, SIAM Journal of Discrete Mathematics, 1(2000), 56-63.
[60] Hoogeveen, H. and van de velde, S. L., Scheduling with target start times, European Journal of Operational Reaearch, 129 (2001), 87-94.
[61] Jain, A. K. and Elmaraghy, H. A., production scheduling/rescheduling in flexible manufacturing, International Journal of Production Research, 35(1997), 281-309.
[62] Kanet, J. J., Minimizing the average deviation of job completion times about a common due date, Naval Research Logistic Quarter/y, 28(1981), 643-651.
[63] Koulamas, C. and Kyparisis, G. J., Single machine scheduling with release times, deadlines and tardiness objectives, European Journal of Operational Research, 133 (2001), 447-453.
[64] Lauff, V. and Werner, F., On the complexity and some properties of multi-stage scheduling problems with earliness and tardiness penalties, Computers and Operations Research, 31 (2004), 317-345.
[65] Lawler, E. L., A "pseudopolynomial" algorithm for sequencing jobs to minimize total tardiness, Annals of Discrete Mathmatics, 1 (1977), 331-342.
[66] Lawler, E. L., Combinatorial Optimization: Networks and Matroids, Holt, Rinehart & Winston, New York, 1976.
[67] Lawler, E. L., Optimal sequencing of a single machine subject to precedence constraints, Management Science, 19 (1973), 544-546.
[68] Lawler, E. L., Sequencing jobs to minimize total weighted completion time subject to precedence constraints, Annals of Discrete Mathematics, 2 (1978), 75-90.
[69] Lee, C. Y., Uzsoy, R. and Martin-Vega, L. A., Efficient algorithms for scheduling semiconductor burn-in operations, Operations Research, 40 (1992), 764-775.
[70] Lee, C. Y. and Vairaktarakis, G. L., Complexity of single machine hierarchical scheduling: A survey, In: Complexity in Numerical Optimization (P. M. Pardalos edits), World Scientific Publishing Company, New Jersey, (1993), 269-298.
[71] Lenstra, J. K., Rinnooy Kan, A. H. G. and Brucker, P., Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1 (1977), 343-362.
[72] Li, R., Shyu, Y. and Adiga, S., A heuristic rescheduling algorithm for computer-based production scheduling system, International Journal of Production Research, 31 (1993), 1815-1826.
[73] Li, S. G., Li, G. J., Wang, X. L. and Liu, Q. M., Minimizing makespan on a single batching machine with release times and non-identical job sizes, Operations Research Letters, 33 (2005), 157-164.
[74] Lin, B. M. T., The strong NP-hardness of two-stage flowshop scheduling with a common second-stage machine, Computers & Operations Research, 26 (1999), 695-698.
[75] Liu, Z. H. and Cheng, T. C. E., Approximation schemes for minimizing total (weighted) completion time with release dates on a batch machine, Theoretical Computer Science, 347 (2005), 288-298.
[76] Liu, Z. H. and Yu, W. C., Scheduling one batch processor subject to job release dates, Discrete Applied Mathematics, 105 (2000), 129-136.
[77] Liu, Z. H., Yuan, J. J. and Cheng, T. C. E., On scheduling an unbounded batch machine, Operations Research Letters, 31 (2003), 42-48.
[78] Mason, A. J. and Anderson, E. J., Minimizing flow time on a single machine with job classes and setup times, Naval Research Logistics, 38 (1991), 333-350.
[79] Mehta, S. V. and Uzsoy, R., Prodictable scheduling of a single machine bubject to breakdowns, Internat. J. Comput. Integrated Manufacturing, 12 (1999), 15-38.
[80] Moukrim, A., Optimal scheduling on parallel machines for a new order class, Operations Research Letters, 24 (1999), 91-95.
[81] Naroska, E., Schwiegelshohn, U., On an on-line scheduling problem for Parallel jobs, Theoretical Computer Science, 81 (2002), 297-304.
[82] Nelson, R. T., Sarin, R. K. and Daniels, R. L., Scheduling with multiple performance measures: The one-machine case, Management Science, 4 (1986), 464-479.
[83] Ng, C. T., Cheng, T. C. E. and Yuan, J. J., A note on the single machine serial batching scheduling problem to minimize maximum lateness with precedence constraints, Operation Research Letters, 30 (2002), 66-68.
[84] Ng, C. T., Cheng, T. C. E. and Yuan, J. J., Strong NP-hardness of the single machine multi-opteration jobs total completion time scheduling problem, Information Processing Letters, 82 (2002), 187-191.
[85] Ng, C. T., Cheng, T. C. E., Yuan, J. J. and Liu, Z. H., On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times, Operation Research Letters, 31(2003), 323-326.
[86] Naroska, E., Schwiegelshohn, U., On an on-line scheduling problem for Parallel jobs, Theoretical Computer Science, 81 (2002), 297-304.
[87] O'Donovan, R., Uzsoy, R. and Mckay, K. N., Predictable scheduling of a single machine with breakdown and sensitive jobs, Int. J. Production Research, 37 (1999), 4217-4233.
[88] Panwalkar, S. S., Smith, M. L. and Seidmann, A., Common due date assignment to minimize total penalty for the one machine scheduling problem of single machine, Operational Research, 30 (1982), 391-399.
[89] Papadimitriou, C. H. and Steiglitz, K., Combinatorial Optimization: Algorithms and Cornplexity, Prentice-Hall, Englewood Cliffs, NJ, 1982.
[90] Phillips, C., Stein, C. and Wein, J., Minimizing average completion time in the presence of release dates, Mathematical Programming, 82 (1998), 199-223.
[91] Potts, C. N. and Kovalyov, M. Y., Scheduling with batching: a review, European Journal of Operational Research, 120 (2000), 228-249.
[92] Pinedo, M., Scheduling: Theory, Algorithms and Systems, Prentice-Hall, Englewood Cliffs, NJ, 1995.
[93] Raman, N., Talbot, F. B. and Rachamadugu, R. V., Due date based scheduling in a general flexible manufacturing system, Journal of Oper. Management, 8 (1989), 115-132.
[94] Raghavachari, M., A V-shape property of optimal schedule of jobs about a common due date, European Journal of Operational Research, 23 (1986), 401-402.
[95] Santos, C. A. and Magazing, M., Batching in single operation manufacturing systems, Operations Research Letters, 4 (1985), 99-103.
[96] Schutten, J. M. J., van de Velde, S. L. and Zijm, W. H. M., Single machine scheduling with release dates, due dates and family setup times, Managernent Science, 42 (1996), 1165-1174.
[97] Schuurman, P. and Woeginger, G. J., Polynomial time approximation algorithms for machine scheduling: ten open problems, Journal of Scheduling, 2 (1999), 203-213.
[98] Shallcross, D., A polynomial algorithm for a one machine batching problem, Operations Research Letters, 11(1992), 213-218.
[99] Simons, B., Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines, SIAM Journal on Computing, 12(2) (1983), 294-299.
[100] Skutella, M. and Woeginger, G. J., A PTAS for minimizing the total weighted completion time on identical parallel machines, Mathematics of Operations Research, 1 (2000), 63-75.
[101] Scharbrodt, M., Steger, A. and Weisser, H., Approximability of scheduling with fixed jobs, Journal of scheduling, 3(1999), 267-284.
[102] T'kindt, V. and Billaut, J. C., Multicriteria Scheduling: Theory, Models and Algorithms, Springer, Berlin, 2002.
[103] 唐恒永，赵传立，排序引论，科学出版社，2002．
[104] 唐国春，张峰，罗守成，刘丽丽，现代排序论，上海科学普及出版社，2003．
[105] Ullman, J. D., NP-complete scheduling problems, Journal of Computer and System Sciences, 10 (1975), 384-393.
[106] Unal, A. T., Uzsoy, R. and Kiran, A. S., Rescheduling on a single machine with parttype depend setup times and deadlines, Annals of Operations Research, 70 (1997), 93-113.
[107] Uzsoy, R., Scheduling batch processing machines with incompatible job families, Int. J. Prod. Res., 33 (1995), 2685-2708.
[108] Van Wassenhove, L. N. and Gelders, L. F., Solving a bicriteria scheduling problem, European Journal of Operational Research, 4 (1980), 42-48.
[109] Webster, S. T., The complexity of scheduling job families about a common due date, Operations Research Letters, 20 (1997), 65-74.
[110] Webster, S. T. and Baker, K. R., Scheduling groups of jobs on a single machine, Operations Research, 43 (1995), 692-703.
[111] Williams, D. and Wirth, A., A new heuristic for a single machine scheduling problem with set-up times, Journal of the Operational Research Society, 47 (1996), 175-180.
[112] Wu, S. D., Storer, R. H. and Chang, P. C., A rescheduling procedure for manufacturing systems under random disruptions. G. Fandel, T. Gulledge, A. Jone, eds. New Directions for Operations Research in Manufacturing. Springer, Berlin, Germany, (1992), 292-308.
[113] Wu, S. D., Storer, R. H. and Chang, P. C., One-machine rescheduling heuristics with efficiency and stability as criteria, Comput. Oper. Res., 20 (1993), 1-14.
[114] Yuan, J. J. and Lin, Y. X., Single machine preemptive scheduling with fixed jobs to minimize tardiness related criteria, European Journal of Operational Research, 164 (2005), 851-855.
[115] 原晋江，林诒勋，关于具有主次指标的单机排序的注记，高校应用数学学报，第11卷第2期(1996)，207-212．
[116] Yuan, J. J., Liu, Z. H., Ng, C. T. and Cheng, T. C. E., The single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan, Theoretical Computer Science, 320 (2004), 199-212.
[117] Yellig, E. J. and Mackulak, G. T., Robust deterministic scheduling in stochastic environments: the method of capacity hedge points, International Journal of Production Research, 35(1997), 369-379.
[118] 越民义，组合优化导论，浙江科学技术出版社，2001．
[119] Zdrzalka, S., Analysis of approximation algorithms for single-machine scheduling with delivery times and sequence independent batch setup times, European Journal of Operational Research, 80 (1995), 371-380.
[120] Zhang,G.C, Cai,X.Q., Lee,C.Y. and Wong,C.K., Minimizing makespan on a single batch processing machine with nonidentical job sizes, Naval Research Logistics, 48 (2001), 226-240.
[121] Zhang,G.C, Cai,X.Q. and Wong,C.K., On-line algorithms for minimizing makespan on batch processing machines, Naval Research Logistics, 48 (2001), 241-258.