• Previous Article
    Variance-optimal hedging for target volatility options
  • JIMO Home
  • This Issue
  • Next Article
    A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors
January  2014, 10(1): 219-241. doi: 10.3934/jimo.2014.10.219

A survey of single machine scheduling to minimize weighted number of tardy jobs

1. 

Department of Mathematics, University of Lagos, Akoka, Yaba, Lagos, Nigeria

2. 

School of Mathematics, Statistics & Computer Science, University of Kwazulu-Natal, Private Bag X5400, Durban, 4000, South Africa

Received  January 2012 Revised  March 2013 Published  October 2013

This paper presents a review of single machine scheduling to minimize the weighted number of tardy jobs. The problem involves processing n jobs on a single machine, each having processing time $p_j$ and due date $d_j$. The aim is to schedule the jobs to meet their due date. A job is tardy if the completion time of job $j$ is $C_j>d_j$ and on-time otherwise. This paper assesses works done to minimize the weighted number of tardy jobs by providing an extensive review of authors, methods and techniques used. Finally, the possible direction for future research is presented.
Citation: Muminu O. Adamu, Aderemi O. Adewumi. A survey of single machine scheduling to minimize weighted number of tardy jobs. Journal of Industrial & Management Optimization, 2014, 10 (1) : 219-241. doi: 10.3934/jimo.2014.10.219
References:
[1]

M. O. Adamu and O. Abass, Scheduling agreeable jobs on a single machine to minimize weighted number of early and tardy jobs,, Journal of Applied Science and Technology, 12 (2007), 12. doi: 10.4314/jast.v12i1.17464.

[2]

A. Agnetics, D. Pacciarelli and A. Pacific, Multi-agent single machine scheduling,, Annals of Operations Research, 150 (2007), 3. doi: 10.1007/s10479-006-0164-y.

[3]

S. Albers and P. Brucker, The complexity of one machine batching problem,, New frontiers in the theory and practice of combinatorial optimization: Applications in manufacturing and VLSI design (Ankara, 47 (1993), 87. doi: 10.1016/0166-218X(93)90085-3.

[4]

A. Allahverdi, J. N. D. Gupta and T. Aldowaisan, A review of scheduling research involving setup considerations,, OMEGA The International Journal of Management Science, 27 (1999), 219. doi: 10.1016/S0305-0483(98)00042-5.

[5]

A. Allahverdi, C. T. Ng, T. C. E. Cheng and M. Y. Kovalyov, A survey of scheduling problems with setup times or costs,, European Journal of Operational Research, 187 (2008), 985. doi: 10.1016/j.ejor.2006.06.060.

[6]

M. B. Aryanezhad, A. Jabbarzadeh and A. Zareei, Combination of genetic algorithm and lp-metric to solve machine bi-criteria scheduling problem,, Proceedings of IEEF IEEM, (2009), 1915. doi: 10.1109/IEEM.2009.5373207.

[7]

M. Azizoglu, M. Koksalan and S. K. Koksalan, Scheduling to minimize maximum earliness and number of tardy jobs where machine idle time is allowed,, Journal of Operational Research Society, 54 (2003), 661.

[8]

K. R. Baker and G. D. Scudder, Scheduling with earliness and tardiness penalties: A review,, Operations Research, 38 (1990), 22. doi: 10.1287/opre.38.1.22.

[9]

S. J. Baluk, Scheduling to minimize the number of late jobs when set-up and processing times are uncertain,, Management Science, 19 (1973), 1283.

[10]

P. Baptiste, Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times,, Journal of Scheduling, 2 (1999), 245. doi: 10.1002/(SICI)1099-1425(199911/12)2:6<245::AID-JOS28>3.0.CO;2-5.

[11]

P. Baptiste, An $O(n^4)$ algorithm for preemptive scheduling of a single machine to minimize the number of late jobs,, Operations Research Letters, 24 (1999), 175. doi: 10.1016/S0167-6377(98)00045-5.

[12]

P. Baptiste, Batching identical jobs,, Mathematical Methods of Operations Research, 52 (2000), 355. doi: 10.1007/s001860000088.

[13]

P. Baptiste, P. Brucker, S. Knust and V. G. Timkovsky, Ten notes on equal processing time scheduling,, 40R, 2 (2004), 111. doi: 10.1007/s10288-003-0024-4.

[14]

P. Baptiste, M. Chrobak and C. Durr, Preemptive scheduling of equal-length jobs to maximize weighted throughput,, Operational Research Letters, 32 (2004), 258. doi: 10.1016/j.orl.2003.09.004.

[15]

P. Baptiste, F. D. Croce, A. Grosso and V. Tkindt, Sequencing a single machine with due dates and deadlines: An ilp-based approach to solve very large instances,, Journal of Scheduling, 13 (2010), 39. doi: 10.1007/s10951-008-0092-6.

[16]

P. Baptiste, L. Peridy and E. Pinson, A branch and bound to minimize the number of late jobs on a single machine with release time constraints,, European Journal of Operational Research, 144 (2003), 1. doi: 10.1016/S0377-2217(01)00353-8.

[17]

M. Ben-Daya, S. O. Duffuaa and A. Raouf, Minimizing mean tardiness subject to unspecified minimum number tardy for a single machine,, European Journal of Operational Research, 89 (1996), 100.

[18]

O. J. Boxma and F. G. Forst, Minimizing the expected weighted number of tardy jobs in stochastic flow shops,, Operations Research Letters, 5 (1986), 119. doi: 10.1016/0167-6377(86)90084-2.

[19]

P. Brucker and M. Y. Kovalyov, Single machine batch scheduling to minimize the weighted number of late jobs,, Mathematical Methods of Operations Research, 43 (1996), 1. doi: 10.1007/BF01303431.

[20]

P. Brucker and S. A. Kravchenko, Scheduling equal processing time jobs to minimize the weighted number of late jobs,, Journal of Mathematical Modeling and Algorithms, 5 (2006), 143. doi: 10.1007/s10852-005-9011-4.

[21]

P. Brucker, A. Gladky, H. Hoogeveen, M. V. Kovalyov, C. N. Potts, T. Tautenhahn and S. L. Van De Velde, Scheduling a batching machine,, Journal of Scheduling, 1 (1998), 31. doi: 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R.

[22]

P. Brucker and S. Knust, Complexity results for scheduling problems,, , ().

[23]

J. Bruno and P. Downey, Complexity of task sequencing with deadlines, set-up times, and changeover costs,, SIAM Journal of Computing, 7 (1978), 393. doi: 10.1137/0207031.

[24]

J. Carlier, Problemes dordonnancement dures gales,, QUESTIO, 5 (1981), 219.

[25]

S. Chand and H. Schneeberger, Single machine scheduling to minimize weighted earliness subject to no tardy jobs,, European Journal of Operational Research, 34 (1988), 221. doi: 10.1016/0377-2217(88)90356-6.

[26]

P. C. Chang and L. H. Su, Scheduling $n$ jobs on one machine to minimize the maximum lateness with a minimum number of tardy jobs,, Computers and Industrial Engineering, 40 (2001), 349. doi: 10.1016/S0360-8352(01)00035-3.

[27]

C. L. Chen and R. L. Bulfin, Complexity of single machine multicriteria scheduling problems,, European Journal of Operational Research, 70 (1993), 115.

[28]

W. Y. Chen and G. J. Sheen, Single machine scheduling with multiple performance measures: Minimizing job-dependent earliness and tardiness subject to the number of tardy jobs,, International Journal of Production Economics, 109 (2007), 214. doi: 10.1016/j.ijpe.2007.01.001.

[29]

T. C. E. Cheng, Z. L. Chen and C. L. Li, Single machine scheduling with trade-off between number of tardy jobs and resource allocation,, Operations Research Letters, 19 (1996), 237. doi: 10.1016/S0167-6377(96)00035-1.

[30]

T. C. E. Cheng, Q. Ding and B. M. T. Lin, A concise survey of scheduling with time-dependent processing times,, European Journal of Operational Research, 152 (2004), 1. doi: 10.1016/S0377-2217(02)00909-8.

[31]

T. C. E. Cheng and M. Gupta, Survey of scheduling research involving due date assignment,, European Journal of Operational Research, 38 (1988), 156. doi: 10.1016/0377-2217(89)90100-8.

[32]

T. C. E. Cheng, J. N. D. Gupta and G. Wang, A review of flowshop scheduling research with setup times,, Production and Operations Management, 9 (2000), 262. doi: 10.1111/j.1937-5956.2000.tb00137.x.

[33]

T. C. E Cheng, C. T. Ng and J. J Yuan, Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs,, Theoretical Computer Science, 362 (2006), 273. doi: 10.1016/j.tcs.2006.07.011.

[34]

M. Chrobak, C. Drr, W. Jawor, L. Kowalik and M. Kurowski, A note on scheduling equal length jobs to maximize throughput,, Journal of Scheduling, 9 (2006), 85. doi: 10.1007/s10951-006-5595-4.

[35]

R. W. Conway, W. L. Maxwell and L. W. Miller, "Theory of Scheduling,", Addison-Wesley, (1967).

[36]

H. A. Crauwels, C. N. Potts, D. V. Oudheusden and L. N. Wassenhove, Branch and bound algorithms for single machine scheduling with batching to minimize the number of late jobs,, Journal of Scheduling, 8 (2005), 161. doi: 10.1007/s10951-005-6365-4.

[37]

H. A. J. Crauwels, C. N. Potts and L. N. Van Wessenhove, Local search heuristics for single machine scheduling with batching to minimize the number of late jobs,, European Journal of Operational Research, 90 (1996), 200. doi: 10.1016/0377-2217(95)00349-5.

[38]

R. L. Daniels and R. K. Sarin, Single Machine Scheduling with Controllable Processing Times and Number of Jobs tardy,, Operations Research, 37 (1989), 981. doi: 10.1287/opre.37.6.981.

[39]

S. Dauzère-Pérès, Minimizing late jobs in the general one machine scheduling problem,, European Journal of Operational Research, 81 (1995), 134. doi: 10.1016/0377-2217(94)00116-T.

[40]

S. Dauzère-Pérès and M. Sevaux, Using lagrangean relaxation to minimize the weighted number of late jobs on a single machine,, Naval Research Logistics, 50 (2003), 273. doi: 10.1002/nav.10056.

[41]

P. De, J. B. Ghosh and C. E. Wells, On the minimization of the weighted number of tardy jobs with random processing times and deadlines,, Computer and Operations Research, 18 (1991), 457. doi: 10.1016/0305-0548(91)90022-J.

[42]

G. Diepen, J. M. V. Akker and J. A. Hoogeveen, Minimizing total weighted tardiness on a single machine with release dates and equal length jobs,, Institute of Information and Computing Sciences, (2005).

[43]

V. R. Dondeti and B. B. Mohanty, Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs,, European Journal of Operational Research, 105 (1998), 509.

[44]

S. O. Duffuaa, A. Raouf, M. Ben-Daya and M. Makki, One machine scheduling to minimize mean tardiness with minimum number of tardy,, Production Planning and Control, 8 (1997), 226. doi: 10.1080/095372897235271.

[45]

H. Emmons, A simplified algorithm for sequencing n jobs on one machine to minimize the number of late jobs,, Technical Report, (1958).

[46]

E. Erel and J. B. Ghosh, Batch scheduling to minimize the weighted number of tardy jobs,, Computers and Industrial Engineering, 53 (2007), 394. doi: 10.1016/j.cie.2007.03.006.

[47]

S. French, "Sequencing and Scheduling: An Introduction to the Mathematics of the Job Shop,", Ellis Harwood, (1982).

[48]

M. R. Garey and D. S. Johnson, "Computers and Intractability, A Guide to the Theory Of NP Completeness,", A Series of Books in the Mathematical Sciences. W. H. Freeman and Co., (1979).

[49]

M. R. Garey and D. S. Johnson, Scheduling tasks with nonuniform deadlines on two processors,, Journal of ACM 23 (1976), 23 (1976), 461. doi: 10.1145/321958.321967.

[50]

R. L. Graham, E. L. Lawler, T. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey,, Annals of Discrete Mathematics., 5 (1979), 287. doi: 10.1016/S0167-5060(08)70356-X.

[51]

J. N. D. Gupta and J. C. Ho, Scheduling with two job classes and setup times to minimize the number of tardy jobs,, International Journal of Production Economics, 42 (1995), 205. doi: 10.1016/0925-5273(95)00156-5.

[52]

N. G. Hall and C. N. Potts, Supply chain scheduling: Batching and delivery,, Operations Research, 51 (2003), 566. doi: 10.1287/opre.51.4.566.16106.

[53]

N. G. Hall and C. N. Potts, The coordination of scheduling and batch deliveries,, Annals of Operations Research, 135 (2005), 41. doi: 10.1007/s10479-005-6234-8.

[54]

N. G. Hall, "Private Communication,", 2006., ().

[55]

A. M. A Hariri and C. N. Potts, Single machine scheduling with deadlines to minimize the weighted number of tardy jobs,, Management, 40 (1994), 1712. doi: 10.1287/mnsc.40.12.1712.

[56]

D. S. Hochbaum and D. Landy, Scheduling with batching: Minimizing the weighted number of tardy jobs,, Operations Research Letters, 16 (1994), 79. doi: 10.1016/0167-6377(94)90063-9.

[57]

D. S. Hochbaum and R. Shamir, Minimizing the number of tardy job units under release time constraints,, Discrete Applied Mathematics, 28 (1990), 45. doi: 10.1016/0166-218X(90)90093-R.

[58]

H. Hoogeveen, Multicriteria scheduling,, European Journal of Operational Research, 167 (2005), 592. doi: 10.1016/j.ejor.2004.07.011.

[59]

H. Hoogeveen, C. N. Potts and G. J. Woeginger, On-line scheduling on a single machine: Maximizing the number of early jobs,, Operational Research Letters, 27 (2000), 193. doi: 10.1016/S0167-6377(00)00061-4.

[60]

W. Huang and F. Zhang, One machine batching problem with due dates to minimize the weighted number of delayed jobs,, 1997. Unpublished paper., ().

[61]

W. Huang, S. Li and G. Tang, A single machine scheduling problem to minimize the weighted number of late jobs and crashed jobs,, International Journal of Operations and Quantitative Management, 4 (1998), 151.

[62]

Y. Huo, J. Y. T. Leung and H. Zhao, Complexity of two-dual criteria scheduling problems,, Operations Research Letters, 35 (2007), 211. doi: 10.1016/j.orl.2006.01.007.

[63]

Y. Huo, J. Y. T. Leung and H. Zhao, Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness,, European Journal of Operational Research, 177 (2007), 116. doi: 10.1016/j.ejor.2005.06.067.

[64]

A. S. Jain and S. Meeran, Deterministic job shop scheduling: Past, present and future,, European Journal of Operational Research, 113 (1999), 390. doi: 10.1016/S0377-2217(98)00113-1.

[65]

W. Jang and C. M. Klein, Minimizing the expected number of tardy jobs when processing times are normally distributed,, Operations Research Letters, 30 (2002), 100. doi: 10.1016/S0167-6377(02)00110-4.

[66]

W. Jang, Dynamic scheduling of stochastic jobs on a single machine,, European Journal of Operational Research, 138 (2002), 518. doi: 10.1016/S0377-2217(01)00174-6.

[67]

F. Jolai, Minimizing number of tardy jobs on a batch processing machine with incompatible job families,, European Journal of Operational Research, 162 (2005), 184. doi: 10.1016/j.ejor.2003.10.011.

[68]

F. Jolai, M. Rabbani, S. Amalnick, A. Dabaghi, M. Dehghan and M. Y. Parast, Genetic algorithm for bi-criteria single machine scheduling problem of minimizing maximum earliness and number of tardy jobs,, Applied Mathematics and Computation, 194 (2007), 552. doi: 10.1016/j.amc.2007.04.063.

[69]

Y. S. Jung, H. Nagasawa and N. Nishiyama, Extension of deterministic scheduling to stochastic scheduling,, Osaka Prefecture University Education and Research Archives, 40 (1991), 265.

[70]

E. K. Karasakal and M. Koksalan, A simulated annealing approach to bicriteria scheduling problems on a single machine,, Journal of Heuristics, 6 (2000), 311.

[71]

R. M. Karp, Reducibility among combinatorial problems,, Complexity of Computer Computations (Proc. Sympos., (1972), 85.

[72]

H. Kise and T. Ibaraki, On balut's algorithm and np-completeness for a chance-constrained scheduling problem,, Management Science, 29 (1983), 384. doi: 10.1287/mnsc.29.3.384.

[73]

H. Kise, T. Ibaraki and H. Mine, A solvable case of the one machine scheduling problem with ready and due times,, Operations Research, 26 (1978), 121. doi: 10.1287/opre.26.1.121.

[74]

M. Koksalan and A. B. Keha, Using genetic algorithms for single machine bicriteria scheduling problems,, European Journal of Operational Research, 145 (2003), 543. doi: 10.1016/S0377-2217(02)00220-5.

[75]

S. K. Kondakci and T. Bekirglu, Scheduling with bicriteria: Total flowtime and number of tardy jobs,, International Journal of Production Economics, 53 (1997), 91.

[76]

S. Kravchenko and F. Werner, Parallel machine problems with equal processing times: A survey,, J. Sched. 14 (2011), 14 (2011), 435. doi: 10.1007/s10951-011-0231-3.

[77]

A. Lann and G. Mosheiov, Single machine scheduling to minimize the number of early and tardy jobs,, Computers and Operational Research, 23 (1996), 769. doi: 10.1016/0305-0548(95)00078-X.

[78]

E. L. Lawler and J. M. Moore, A functional equation and its applications to resource allocation and sequencing problems,, Management Science, 16 (1969), 77. doi: 10.1287/mnsc.16.1.77.

[79]

E. L. Lawler, Sequencing to minimize the weighted number of tardy jobs,, Rev. Francaise Automat. Recherche Operationnelle, 10 (1976), 27.

[80]

E. L. Lawler, Scheduling a single machine to minimize the number of late jobs,, Report CSD-83-139, (1983), 83.

[81]

E. L. Lawler, A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs,, Annals of Operations Research, 26 (1990), 125. doi: 10.1007/BF02248588.

[82]

E. L. Lawler, Knapsack-like scheduling problems, the moore-hudgson algorithm and the tower of sets property,, Mathl. Comput. Modelling, 20 (1994), 91. doi: 10.1016/0895-7177(94)90209-7.

[83]

E. L. Lawler, J. K Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys, Sequencing and scheduling: Algorithms and complexity, In: S.C. Graves, A.H.G. Rinnooy Kan and P.H. Zipkin (Eds),, Logistics of Production and Inventory, (1993), 445.

[84]

C. Y. Lee and G. L. Vairaktarakis, Complexity of single machine hierarchical scheduling: A survey,, Complexity in Numerical Optimization, 19 (1993), 269.

[85]

D. Lei, Multi-objective production scheduling: A survey,, International Journal of Advance Manufacturing Technology, 43 (2009), 926. doi: 10.1007/s00170-008-1770-4.

[86]

J. K. Lenstra and A. H. G. Rinnooy Kan, Complexity results for scheduling chains on a single machine,, European Journal of Operational Research, 4 (1980), 270. doi: 10.1016/0377-2217(80)90111-3.

[87]

J. K. Lenstra, "Production Scheduling,", Mathematisch Centrum, (1977).

[88]

J. K. Lenstra, A. H. G. Rinnooy Kan and P. Brucker, Complexity of machine scheduling problems,, Annals of Discrete Mathematics, 1 (1977), 343.

[89]

C. L. Li, T. C. E. Cheng and Z. L. Chen, Single machine scheduling to minimize the weighted number of early and tardy agreeable jobs,, Computers and Operations Research, 22 (1995), 205. doi: 10.1016/0305-0548(94)E0012-V.

[90]

S. Li, Z. L. Chen and G. Tang, A note on the optimality proof of the kise-ibaraki-mine algorithm,, Operations Research, 58 (2010), 508. doi: 10.1287/opre.1090.0749.

[91]

S. Li, C. T. Ng and J. Yuan, Scheduling deteriorating jobs with CON/SLK due date assignment on a single machine,, International Journal of Production Economics, 131 (2011), 747. doi: 10.1016/j.ijpe.2011.02.029.

[92]

B. M. T. Lin and T. C. E. Cheng, Minimizing the weighted number of tardy jobs and maximum tardiness in relocation problem with due dates constraints,, European Journal of Operational Research, 116 (1999), 183. doi: 10.1016/S0377-2217(98)00196-9.

[93]

L. Liu and F. Zhang, Minimizing number of tardy jobs on a batch processing machine with incompatible job families,, ISECS International Colloquium on Computing, 3 (2008), 277. doi: 10.1109/CCCM.2008.107.

[94]

Y. Ma, C. B. Chu and C. R. Zuo, A survey scheduling with deterministic machine availability constraints,, Computers and Industrial Engineering, 58 (2010), 199. doi: 10.1016/j.cie.2009.04.014.

[95]

R. M'Hallah and R. L. Bulfin, Minimizing the weighted number of tardy jobs on a single machine with release dates,, European Journal of Operational Research, 176 (2007), 727. doi: 10.1016/j.ejor.2005.08.013.

[96]

R. M'Hallah and R.L. Bulfin, Minimizing the weighted number of tardy jobs on a single machine,, European Journal of Operational Research, 145 (2003), 45. doi: 10.1016/S0377-2217(02)00180-7.

[97]

M. Mathirajan and A. J. Sivakumar, A literature review, classification and simple meta-analysis on scheduling of batch processors in semi-conductor,, International Journal of Advance Manuf. Technology, 29 (2006), 990.

[98]

W. L. Maxwell, On sequencing n jobs on one machine to minimize the number of late jobs,, Management Science, 16 (1970), 295.

[99]

M. M. Mazdeh, A. Hamidinia and A. Karamouzian, A mathematical model for weighted tardy jobs scheduling problem with a batched delivery system,, International Journal of Industrial Engineering Computations, 2 (2011), 491.

[100]

E. Molaee, G. Moslehi and M. Reisi, Minimizing maximum earliness and number of tardy jobs in the single machine scheduling problem,, Computers and Mathematics with Applications, 60 (2010), 2909. doi: 10.1016/j.camwa.2010.09.046.

[101]

C. L. Monma and C. N. Potts, On the complexity with batch set-up times,, Operations Research, 37 (1989), 798. doi: 10.1287/opre.37.5.798.

[102]

J. M. Moore, An $n$ job, one machine sequencing algorithm for minimizing the number of late jobs,, Management Science, 15 (1968), 102. doi: 10.1287/mnsc.15.1.102.

[103]

A. Nagar, J. Haddock and S. Heragu, Multiple and bicriteria scheduling: A literature survey,, European Journal of Operational Research, 81 (1995), 88. doi: 10.1016/0377-2217(93)E0140-S.

[104]

R. T. Nelson, R. K. Sarin and R. L. Daniels, Scheduling with multiple performance measures: The one machine case,, Management Science, 32 (1986), 464. doi: 10.1287/mnsc.32.4.464.

[105]

S. Ourari, C. Briand and B. Bouzouia, A MIP approach for the minimization of the number of late jobs in single machine scheduling,, Journal of Math. Modeling and Algorithms. To appear, (2009).

[106]

S. Pathumnakul and P. J. Egbelu, Algorithm for minimizing weighted earliness penalty in single machine problem,, European Journal of Operational Research, 161 (2005), 780. doi: 10.1016/j.ejor.2003.07.017.

[107]

L. Peridy, E. Pinson and D. Rivreau, Using short-term memory to minimize the weighted number of late jobs on a single machine,, European Journal of Operational Research, 148 (2003), 591. doi: 10.1016/S0377-2217(02)00438-1.

[108]

M. Pinedo, stochastic scheduling with release dates and due dates,, Operations Research, 31 (1983), 559. doi: 10.1287/opre.31.3.559.

[109]

C. N. Potts and M. V. Kovalyov, Scheduling with batching: A review,, Fifteenth EURO Summer Institute. Production Scheduling: Deterministic, 120 (2000), 228. doi: 10.1016/S0377-2217(99)00153-8.

[110]

C. N. Potts and V. Wassenhove, Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity,, Journal of Operations Research Society, 43 (1992), 395.

[111]

C. N. Potts and V. Wassenhove, Algorithms for scheduling a single machine to minimize the weighted number of late jobs,, Management Science, 34 (1988), 843. doi: 10.1287/mnsc.34.7.843.

[112]

J. Ren, Y. Zhang, X. Zhang and G. Sun, Approximation algorithms for minimizing the weighted number of tardy jobs on a batch machine,, Combinatorial optimization and applications, (2009), 403. doi: 10.1007/978-3-642-02026-1_38.

[113]

A.H.G. Rinnooy Kan, "Machine Scheduling Problems: Classification, Complexity and Computations,", Nijhoff, (1976).

[114]

G. Rote and G. J. Woeginger, Minimizing the number of tardy jobs on a single machine with batch setup time,, ACTA Cybernetica, 13 (1998), 423.

[115]

R. Sadykov, A hybrid branch and cut for the one dimensional machine scheduling problem,, Lecture notes in Computer Science, 3011 (2004), 409.

[116]

R. Sadykov, A branch and check algorithm for minimizing the weighted number of late jobs on a single machine with release dates,, European Journal of Operational Research, 189 (2008), 1284. doi: 10.1016/j.ejor.2006.06.078.

[117]

S. K. Sahni, Algorithms for scheduling independent tasks,, Journal of Assoc. Comput. Mach, 23 (1976), 116. doi: 10.1145/321921.321934.

[118]

P. Senthilkumar and S. Narayanan, Literature review of single machine scheduling problem with uniform parallel machines,, Intelligent Information Management, 2 (2010), 457. doi: 10.4236/iim.2010.28056.

[119]

D. K. Seo, C. M. Klein and W. Jang, Single machine stochastic scheduling to minimize the expected number of tardy jobs using mathematical programming models,, Computers and Industrial Engineering, 48 (2005), 153. doi: 10.1016/j.cie.2005.01.002.

[120]

M. Sevaux and S. Dauzère-Pérès, Genetic algorithms to minimize the weighted number of late jobs on a single machine,, Meta-heuristics in combinatorial optimization. European Journal of Operational Research, 151 (2003), 296. doi: 10.1016/S0377-2217(02)00827-5.

[121]

D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times,, Discrete Applied Mathematics, 155 (2007), 1643. doi: 10.1016/j.dam.2007.02.003.

[122]

D. Shabtay and G. Steiner, Optimal due date assignment and resource allocation to minimize the weighted number of tardy jobs on a single machine,, Manufacturing and Service Operations Management, 9 (2007), 332. doi: 10.1287/msom.1060.0139.

[123]

D. Shabtay and G. Steiner, Bicriteria models to minimize the total weighted number of tardy jobs with convex controllable processing times and common due date assignment,, Proceedings Multidisciplinary International Conference on Scheduling: Theory and Applications, (2009), 301.

[124]

D. Shabtay and G. Steiner, A bicriteria approach to minimize the total weighted number of tardy jobs with convex controllable processing times and assigning due dates,, Journal of Scheduling, 14 (2011), 455. doi: 10.1007/s10951-010-0208-7.

[125]

A. H. Sharary and N. Zaguia, Minimizing the number of tardy jobs in single machine sequencing,, Discrete Mathematics, 117 (1993), 215. doi: 10.1016/0012-365X(93)90336-R.

[126]

H. M. Soroush, Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem,, European Journal of Operational Research, 181 (2007), 266. doi: 10.1016/j.ejor.2006.05.036.

[127]

G. Steiner and R. Zhang, Minimizing the total weighted number of late jobs with late deliveries in two-level supply chains,, in, (2007), 447. doi: 10.1007/s10951-009-0109-9.

[128]

G. Steiner and R. Zhang, Minimizing the weighted number of late jobs with batch setup times and delivery costs on a single machine,, Multiprocessor Scheduling: Theory and Applications, (2007), 85. doi: 10.5772/5216.

[129]

G. Steiner and R. Zhang, Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains,, Journal of Scheduling, 12 (2009), 565. doi: 10.1007/s10951-009-0109-9.

[130]

G. Steiner, Minimizing the number of tardy jobs with procedence constraints and agreeable due dates,, Models and algorithms for planning and scheduling problems (Loveno di Menaggio, 72 (1997), 167. doi: 10.1016/S0166-218X(96)00043-1.

[131]

L. B. J. M. Sturm, A simple optimality proof of moore's sequencing algorithm,, Management Science, 17 (1970), 116. doi: 10.1287/mnsc.17.1.116.

[132]

G. Tang, A new branch and bound algorithm for minimizing the weighted number of tardy jobs,, Annals of Operations Research, 24 (1990), 225. doi: 10.1007/BF02216825.

[133]

G. L. Vairaktarakis and C. Y. Lee, The single machine scheduling to minimize total tardiness subject to minimum number of tardy jobs,, IIE Transactions, 27 (1995), 250. doi: 10.1080/07408179508936738.

[134]

M. Van der Akker and H. Hoogeveen, Minimizing the number of tardy jobs,, in J. Y.-T. Leung (Ed), (2004).

[135]

F. J. Villarreal and R. L. Bulfin, Scheduling a single machine to minimize the weighted number of tardy jobs,, IE Transactions, 15 (1983), 337. doi: 10.1080/05695558308974657.

[136]

G. Wan and B. P. C. Yen, Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs,, European Journal of Operational Research, 195 (2009), 89. doi: 10.1016/j.ejor.2008.01.029.

[137]

S. Webster and K. R. Baker, Scheduling groups of jobs on a single machine,, Operations Research, 43 (1995), 692. doi: 10.1287/opre.43.4.692.

[138]

W. H. Yang and C. J. Liao, Survey of scheduling research involving setup times,, International Journal of Systems Sciences 30 (1999), 30 (1999), 143. doi: 10.1080/002077299292498.

[139]

B. P. C. Yen and G. Wan, Single machine bicriteria scheduling: A survey,, Industrial Engineering: Theory, 10 (2003), 222.

[140]

W. K. Yeung, C. Oguz and T. C. E. Cheng, Minimizing weighted number of early and tardy jobs with a common due window involving location penalty,, Annals of Operations Research, 108 (2001), 33. doi: 10.1023/A:1016094508744.

show all references

References:
[1]

M. O. Adamu and O. Abass, Scheduling agreeable jobs on a single machine to minimize weighted number of early and tardy jobs,, Journal of Applied Science and Technology, 12 (2007), 12. doi: 10.4314/jast.v12i1.17464.

[2]

A. Agnetics, D. Pacciarelli and A. Pacific, Multi-agent single machine scheduling,, Annals of Operations Research, 150 (2007), 3. doi: 10.1007/s10479-006-0164-y.

[3]

S. Albers and P. Brucker, The complexity of one machine batching problem,, New frontiers in the theory and practice of combinatorial optimization: Applications in manufacturing and VLSI design (Ankara, 47 (1993), 87. doi: 10.1016/0166-218X(93)90085-3.

[4]

A. Allahverdi, J. N. D. Gupta and T. Aldowaisan, A review of scheduling research involving setup considerations,, OMEGA The International Journal of Management Science, 27 (1999), 219. doi: 10.1016/S0305-0483(98)00042-5.

[5]

A. Allahverdi, C. T. Ng, T. C. E. Cheng and M. Y. Kovalyov, A survey of scheduling problems with setup times or costs,, European Journal of Operational Research, 187 (2008), 985. doi: 10.1016/j.ejor.2006.06.060.

[6]

M. B. Aryanezhad, A. Jabbarzadeh and A. Zareei, Combination of genetic algorithm and lp-metric to solve machine bi-criteria scheduling problem,, Proceedings of IEEF IEEM, (2009), 1915. doi: 10.1109/IEEM.2009.5373207.

[7]

M. Azizoglu, M. Koksalan and S. K. Koksalan, Scheduling to minimize maximum earliness and number of tardy jobs where machine idle time is allowed,, Journal of Operational Research Society, 54 (2003), 661.

[8]

K. R. Baker and G. D. Scudder, Scheduling with earliness and tardiness penalties: A review,, Operations Research, 38 (1990), 22. doi: 10.1287/opre.38.1.22.

[9]

S. J. Baluk, Scheduling to minimize the number of late jobs when set-up and processing times are uncertain,, Management Science, 19 (1973), 1283.

[10]

P. Baptiste, Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times,, Journal of Scheduling, 2 (1999), 245. doi: 10.1002/(SICI)1099-1425(199911/12)2:6<245::AID-JOS28>3.0.CO;2-5.

[11]

P. Baptiste, An $O(n^4)$ algorithm for preemptive scheduling of a single machine to minimize the number of late jobs,, Operations Research Letters, 24 (1999), 175. doi: 10.1016/S0167-6377(98)00045-5.

[12]

P. Baptiste, Batching identical jobs,, Mathematical Methods of Operations Research, 52 (2000), 355. doi: 10.1007/s001860000088.

[13]

P. Baptiste, P. Brucker, S. Knust and V. G. Timkovsky, Ten notes on equal processing time scheduling,, 40R, 2 (2004), 111. doi: 10.1007/s10288-003-0024-4.

[14]

P. Baptiste, M. Chrobak and C. Durr, Preemptive scheduling of equal-length jobs to maximize weighted throughput,, Operational Research Letters, 32 (2004), 258. doi: 10.1016/j.orl.2003.09.004.

[15]

P. Baptiste, F. D. Croce, A. Grosso and V. Tkindt, Sequencing a single machine with due dates and deadlines: An ilp-based approach to solve very large instances,, Journal of Scheduling, 13 (2010), 39. doi: 10.1007/s10951-008-0092-6.

[16]

P. Baptiste, L. Peridy and E. Pinson, A branch and bound to minimize the number of late jobs on a single machine with release time constraints,, European Journal of Operational Research, 144 (2003), 1. doi: 10.1016/S0377-2217(01)00353-8.

[17]

M. Ben-Daya, S. O. Duffuaa and A. Raouf, Minimizing mean tardiness subject to unspecified minimum number tardy for a single machine,, European Journal of Operational Research, 89 (1996), 100.

[18]

O. J. Boxma and F. G. Forst, Minimizing the expected weighted number of tardy jobs in stochastic flow shops,, Operations Research Letters, 5 (1986), 119. doi: 10.1016/0167-6377(86)90084-2.

[19]

P. Brucker and M. Y. Kovalyov, Single machine batch scheduling to minimize the weighted number of late jobs,, Mathematical Methods of Operations Research, 43 (1996), 1. doi: 10.1007/BF01303431.

[20]

P. Brucker and S. A. Kravchenko, Scheduling equal processing time jobs to minimize the weighted number of late jobs,, Journal of Mathematical Modeling and Algorithms, 5 (2006), 143. doi: 10.1007/s10852-005-9011-4.

[21]

P. Brucker, A. Gladky, H. Hoogeveen, M. V. Kovalyov, C. N. Potts, T. Tautenhahn and S. L. Van De Velde, Scheduling a batching machine,, Journal of Scheduling, 1 (1998), 31. doi: 10.1002/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R.

[22]

P. Brucker and S. Knust, Complexity results for scheduling problems,, , ().

[23]

J. Bruno and P. Downey, Complexity of task sequencing with deadlines, set-up times, and changeover costs,, SIAM Journal of Computing, 7 (1978), 393. doi: 10.1137/0207031.

[24]

J. Carlier, Problemes dordonnancement dures gales,, QUESTIO, 5 (1981), 219.

[25]

S. Chand and H. Schneeberger, Single machine scheduling to minimize weighted earliness subject to no tardy jobs,, European Journal of Operational Research, 34 (1988), 221. doi: 10.1016/0377-2217(88)90356-6.

[26]

P. C. Chang and L. H. Su, Scheduling $n$ jobs on one machine to minimize the maximum lateness with a minimum number of tardy jobs,, Computers and Industrial Engineering, 40 (2001), 349. doi: 10.1016/S0360-8352(01)00035-3.

[27]

C. L. Chen and R. L. Bulfin, Complexity of single machine multicriteria scheduling problems,, European Journal of Operational Research, 70 (1993), 115.

[28]

W. Y. Chen and G. J. Sheen, Single machine scheduling with multiple performance measures: Minimizing job-dependent earliness and tardiness subject to the number of tardy jobs,, International Journal of Production Economics, 109 (2007), 214. doi: 10.1016/j.ijpe.2007.01.001.

[29]

T. C. E. Cheng, Z. L. Chen and C. L. Li, Single machine scheduling with trade-off between number of tardy jobs and resource allocation,, Operations Research Letters, 19 (1996), 237. doi: 10.1016/S0167-6377(96)00035-1.

[30]

T. C. E. Cheng, Q. Ding and B. M. T. Lin, A concise survey of scheduling with time-dependent processing times,, European Journal of Operational Research, 152 (2004), 1. doi: 10.1016/S0377-2217(02)00909-8.

[31]

T. C. E. Cheng and M. Gupta, Survey of scheduling research involving due date assignment,, European Journal of Operational Research, 38 (1988), 156. doi: 10.1016/0377-2217(89)90100-8.

[32]

T. C. E. Cheng, J. N. D. Gupta and G. Wang, A review of flowshop scheduling research with setup times,, Production and Operations Management, 9 (2000), 262. doi: 10.1111/j.1937-5956.2000.tb00137.x.

[33]

T. C. E Cheng, C. T. Ng and J. J Yuan, Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs,, Theoretical Computer Science, 362 (2006), 273. doi: 10.1016/j.tcs.2006.07.011.

[34]

M. Chrobak, C. Drr, W. Jawor, L. Kowalik and M. Kurowski, A note on scheduling equal length jobs to maximize throughput,, Journal of Scheduling, 9 (2006), 85. doi: 10.1007/s10951-006-5595-4.

[35]

R. W. Conway, W. L. Maxwell and L. W. Miller, "Theory of Scheduling,", Addison-Wesley, (1967).

[36]

H. A. Crauwels, C. N. Potts, D. V. Oudheusden and L. N. Wassenhove, Branch and bound algorithms for single machine scheduling with batching to minimize the number of late jobs,, Journal of Scheduling, 8 (2005), 161. doi: 10.1007/s10951-005-6365-4.

[37]

H. A. J. Crauwels, C. N. Potts and L. N. Van Wessenhove, Local search heuristics for single machine scheduling with batching to minimize the number of late jobs,, European Journal of Operational Research, 90 (1996), 200. doi: 10.1016/0377-2217(95)00349-5.

[38]

R. L. Daniels and R. K. Sarin, Single Machine Scheduling with Controllable Processing Times and Number of Jobs tardy,, Operations Research, 37 (1989), 981. doi: 10.1287/opre.37.6.981.

[39]

S. Dauzère-Pérès, Minimizing late jobs in the general one machine scheduling problem,, European Journal of Operational Research, 81 (1995), 134. doi: 10.1016/0377-2217(94)00116-T.

[40]

S. Dauzère-Pérès and M. Sevaux, Using lagrangean relaxation to minimize the weighted number of late jobs on a single machine,, Naval Research Logistics, 50 (2003), 273. doi: 10.1002/nav.10056.

[41]

P. De, J. B. Ghosh and C. E. Wells, On the minimization of the weighted number of tardy jobs with random processing times and deadlines,, Computer and Operations Research, 18 (1991), 457. doi: 10.1016/0305-0548(91)90022-J.

[42]

G. Diepen, J. M. V. Akker and J. A. Hoogeveen, Minimizing total weighted tardiness on a single machine with release dates and equal length jobs,, Institute of Information and Computing Sciences, (2005).

[43]

V. R. Dondeti and B. B. Mohanty, Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs,, European Journal of Operational Research, 105 (1998), 509.

[44]

S. O. Duffuaa, A. Raouf, M. Ben-Daya and M. Makki, One machine scheduling to minimize mean tardiness with minimum number of tardy,, Production Planning and Control, 8 (1997), 226. doi: 10.1080/095372897235271.

[45]

H. Emmons, A simplified algorithm for sequencing n jobs on one machine to minimize the number of late jobs,, Technical Report, (1958).

[46]

E. Erel and J. B. Ghosh, Batch scheduling to minimize the weighted number of tardy jobs,, Computers and Industrial Engineering, 53 (2007), 394. doi: 10.1016/j.cie.2007.03.006.

[47]

S. French, "Sequencing and Scheduling: An Introduction to the Mathematics of the Job Shop,", Ellis Harwood, (1982).

[48]

M. R. Garey and D. S. Johnson, "Computers and Intractability, A Guide to the Theory Of NP Completeness,", A Series of Books in the Mathematical Sciences. W. H. Freeman and Co., (1979).

[49]

M. R. Garey and D. S. Johnson, Scheduling tasks with nonuniform deadlines on two processors,, Journal of ACM 23 (1976), 23 (1976), 461. doi: 10.1145/321958.321967.

[50]

R. L. Graham, E. L. Lawler, T. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey,, Annals of Discrete Mathematics., 5 (1979), 287. doi: 10.1016/S0167-5060(08)70356-X.

[51]

J. N. D. Gupta and J. C. Ho, Scheduling with two job classes and setup times to minimize the number of tardy jobs,, International Journal of Production Economics, 42 (1995), 205. doi: 10.1016/0925-5273(95)00156-5.

[52]

N. G. Hall and C. N. Potts, Supply chain scheduling: Batching and delivery,, Operations Research, 51 (2003), 566. doi: 10.1287/opre.51.4.566.16106.

[53]

N. G. Hall and C. N. Potts, The coordination of scheduling and batch deliveries,, Annals of Operations Research, 135 (2005), 41. doi: 10.1007/s10479-005-6234-8.

[54]

N. G. Hall, "Private Communication,", 2006., ().

[55]

A. M. A Hariri and C. N. Potts, Single machine scheduling with deadlines to minimize the weighted number of tardy jobs,, Management, 40 (1994), 1712. doi: 10.1287/mnsc.40.12.1712.

[56]

D. S. Hochbaum and D. Landy, Scheduling with batching: Minimizing the weighted number of tardy jobs,, Operations Research Letters, 16 (1994), 79. doi: 10.1016/0167-6377(94)90063-9.

[57]

D. S. Hochbaum and R. Shamir, Minimizing the number of tardy job units under release time constraints,, Discrete Applied Mathematics, 28 (1990), 45. doi: 10.1016/0166-218X(90)90093-R.

[58]

H. Hoogeveen, Multicriteria scheduling,, European Journal of Operational Research, 167 (2005), 592. doi: 10.1016/j.ejor.2004.07.011.

[59]

H. Hoogeveen, C. N. Potts and G. J. Woeginger, On-line scheduling on a single machine: Maximizing the number of early jobs,, Operational Research Letters, 27 (2000), 193. doi: 10.1016/S0167-6377(00)00061-4.

[60]

W. Huang and F. Zhang, One machine batching problem with due dates to minimize the weighted number of delayed jobs,, 1997. Unpublished paper., ().

[61]

W. Huang, S. Li and G. Tang, A single machine scheduling problem to minimize the weighted number of late jobs and crashed jobs,, International Journal of Operations and Quantitative Management, 4 (1998), 151.

[62]

Y. Huo, J. Y. T. Leung and H. Zhao, Complexity of two-dual criteria scheduling problems,, Operations Research Letters, 35 (2007), 211. doi: 10.1016/j.orl.2006.01.007.

[63]

Y. Huo, J. Y. T. Leung and H. Zhao, Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness,, European Journal of Operational Research, 177 (2007), 116. doi: 10.1016/j.ejor.2005.06.067.

[64]

A. S. Jain and S. Meeran, Deterministic job shop scheduling: Past, present and future,, European Journal of Operational Research, 113 (1999), 390. doi: 10.1016/S0377-2217(98)00113-1.

[65]

W. Jang and C. M. Klein, Minimizing the expected number of tardy jobs when processing times are normally distributed,, Operations Research Letters, 30 (2002), 100. doi: 10.1016/S0167-6377(02)00110-4.

[66]

W. Jang, Dynamic scheduling of stochastic jobs on a single machine,, European Journal of Operational Research, 138 (2002), 518. doi: 10.1016/S0377-2217(01)00174-6.

[67]

F. Jolai, Minimizing number of tardy jobs on a batch processing machine with incompatible job families,, European Journal of Operational Research, 162 (2005), 184. doi: 10.1016/j.ejor.2003.10.011.

[68]

F. Jolai, M. Rabbani, S. Amalnick, A. Dabaghi, M. Dehghan and M. Y. Parast, Genetic algorithm for bi-criteria single machine scheduling problem of minimizing maximum earliness and number of tardy jobs,, Applied Mathematics and Computation, 194 (2007), 552. doi: 10.1016/j.amc.2007.04.063.

[69]

Y. S. Jung, H. Nagasawa and N. Nishiyama, Extension of deterministic scheduling to stochastic scheduling,, Osaka Prefecture University Education and Research Archives, 40 (1991), 265.

[70]

E. K. Karasakal and M. Koksalan, A simulated annealing approach to bicriteria scheduling problems on a single machine,, Journal of Heuristics, 6 (2000), 311.

[71]

R. M. Karp, Reducibility among combinatorial problems,, Complexity of Computer Computations (Proc. Sympos., (1972), 85.

[72]

H. Kise and T. Ibaraki, On balut's algorithm and np-completeness for a chance-constrained scheduling problem,, Management Science, 29 (1983), 384. doi: 10.1287/mnsc.29.3.384.

[73]

H. Kise, T. Ibaraki and H. Mine, A solvable case of the one machine scheduling problem with ready and due times,, Operations Research, 26 (1978), 121. doi: 10.1287/opre.26.1.121.

[74]

M. Koksalan and A. B. Keha, Using genetic algorithms for single machine bicriteria scheduling problems,, European Journal of Operational Research, 145 (2003), 543. doi: 10.1016/S0377-2217(02)00220-5.

[75]

S. K. Kondakci and T. Bekirglu, Scheduling with bicriteria: Total flowtime and number of tardy jobs,, International Journal of Production Economics, 53 (1997), 91.

[76]

S. Kravchenko and F. Werner, Parallel machine problems with equal processing times: A survey,, J. Sched. 14 (2011), 14 (2011), 435. doi: 10.1007/s10951-011-0231-3.

[77]

A. Lann and G. Mosheiov, Single machine scheduling to minimize the number of early and tardy jobs,, Computers and Operational Research, 23 (1996), 769. doi: 10.1016/0305-0548(95)00078-X.

[78]

E. L. Lawler and J. M. Moore, A functional equation and its applications to resource allocation and sequencing problems,, Management Science, 16 (1969), 77. doi: 10.1287/mnsc.16.1.77.

[79]

E. L. Lawler, Sequencing to minimize the weighted number of tardy jobs,, Rev. Francaise Automat. Recherche Operationnelle, 10 (1976), 27.

[80]

E. L. Lawler, Scheduling a single machine to minimize the number of late jobs,, Report CSD-83-139, (1983), 83.

[81]

E. L. Lawler, A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs,, Annals of Operations Research, 26 (1990), 125. doi: 10.1007/BF02248588.

[82]

E. L. Lawler, Knapsack-like scheduling problems, the moore-hudgson algorithm and the tower of sets property,, Mathl. Comput. Modelling, 20 (1994), 91. doi: 10.1016/0895-7177(94)90209-7.

[83]

E. L. Lawler, J. K Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys, Sequencing and scheduling: Algorithms and complexity, In: S.C. Graves, A.H.G. Rinnooy Kan and P.H. Zipkin (Eds),, Logistics of Production and Inventory, (1993), 445.

[84]

C. Y. Lee and G. L. Vairaktarakis, Complexity of single machine hierarchical scheduling: A survey,, Complexity in Numerical Optimization, 19 (1993), 269.

[85]

D. Lei, Multi-objective production scheduling: A survey,, International Journal of Advance Manufacturing Technology, 43 (2009), 926. doi: 10.1007/s00170-008-1770-4.

[86]

J. K. Lenstra and A. H. G. Rinnooy Kan, Complexity results for scheduling chains on a single machine,, European Journal of Operational Research, 4 (1980), 270. doi: 10.1016/0377-2217(80)90111-3.

[87]

J. K. Lenstra, "Production Scheduling,", Mathematisch Centrum, (1977).

[88]

J. K. Lenstra, A. H. G. Rinnooy Kan and P. Brucker, Complexity of machine scheduling problems,, Annals of Discrete Mathematics, 1 (1977), 343.

[89]

C. L. Li, T. C. E. Cheng and Z. L. Chen, Single machine scheduling to minimize the weighted number of early and tardy agreeable jobs,, Computers and Operations Research, 22 (1995), 205. doi: 10.1016/0305-0548(94)E0012-V.

[90]

S. Li, Z. L. Chen and G. Tang, A note on the optimality proof of the kise-ibaraki-mine algorithm,, Operations Research, 58 (2010), 508. doi: 10.1287/opre.1090.0749.

[91]

S. Li, C. T. Ng and J. Yuan, Scheduling deteriorating jobs with CON/SLK due date assignment on a single machine,, International Journal of Production Economics, 131 (2011), 747. doi: 10.1016/j.ijpe.2011.02.029.

[92]

B. M. T. Lin and T. C. E. Cheng, Minimizing the weighted number of tardy jobs and maximum tardiness in relocation problem with due dates constraints,, European Journal of Operational Research, 116 (1999), 183. doi: 10.1016/S0377-2217(98)00196-9.

[93]

L. Liu and F. Zhang, Minimizing number of tardy jobs on a batch processing machine with incompatible job families,, ISECS International Colloquium on Computing, 3 (2008), 277. doi: 10.1109/CCCM.2008.107.

[94]

Y. Ma, C. B. Chu and C. R. Zuo, A survey scheduling with deterministic machine availability constraints,, Computers and Industrial Engineering, 58 (2010), 199. doi: 10.1016/j.cie.2009.04.014.

[95]

R. M'Hallah and R. L. Bulfin, Minimizing the weighted number of tardy jobs on a single machine with release dates,, European Journal of Operational Research, 176 (2007), 727. doi: 10.1016/j.ejor.2005.08.013.

[96]

R. M'Hallah and R.L. Bulfin, Minimizing the weighted number of tardy jobs on a single machine,, European Journal of Operational Research, 145 (2003), 45. doi: 10.1016/S0377-2217(02)00180-7.

[97]

M. Mathirajan and A. J. Sivakumar, A literature review, classification and simple meta-analysis on scheduling of batch processors in semi-conductor,, International Journal of Advance Manuf. Technology, 29 (2006), 990.

[98]

W. L. Maxwell, On sequencing n jobs on one machine to minimize the number of late jobs,, Management Science, 16 (1970), 295.

[99]

M. M. Mazdeh, A. Hamidinia and A. Karamouzian, A mathematical model for weighted tardy jobs scheduling problem with a batched delivery system,, International Journal of Industrial Engineering Computations, 2 (2011), 491.

[100]

E. Molaee, G. Moslehi and M. Reisi, Minimizing maximum earliness and number of tardy jobs in the single machine scheduling problem,, Computers and Mathematics with Applications, 60 (2010), 2909. doi: 10.1016/j.camwa.2010.09.046.

[101]

C. L. Monma and C. N. Potts, On the complexity with batch set-up times,, Operations Research, 37 (1989), 798. doi: 10.1287/opre.37.5.798.

[102]

J. M. Moore, An $n$ job, one machine sequencing algorithm for minimizing the number of late jobs,, Management Science, 15 (1968), 102. doi: 10.1287/mnsc.15.1.102.

[103]

A. Nagar, J. Haddock and S. Heragu, Multiple and bicriteria scheduling: A literature survey,, European Journal of Operational Research, 81 (1995), 88. doi: 10.1016/0377-2217(93)E0140-S.

[104]

R. T. Nelson, R. K. Sarin and R. L. Daniels, Scheduling with multiple performance measures: The one machine case,, Management Science, 32 (1986), 464. doi: 10.1287/mnsc.32.4.464.

[105]

S. Ourari, C. Briand and B. Bouzouia, A MIP approach for the minimization of the number of late jobs in single machine scheduling,, Journal of Math. Modeling and Algorithms. To appear, (2009).

[106]

S. Pathumnakul and P. J. Egbelu, Algorithm for minimizing weighted earliness penalty in single machine problem,, European Journal of Operational Research, 161 (2005), 780. doi: 10.1016/j.ejor.2003.07.017.

[107]

L. Peridy, E. Pinson and D. Rivreau, Using short-term memory to minimize the weighted number of late jobs on a single machine,, European Journal of Operational Research, 148 (2003), 591. doi: 10.1016/S0377-2217(02)00438-1.

[108]

M. Pinedo, stochastic scheduling with release dates and due dates,, Operations Research, 31 (1983), 559. doi: 10.1287/opre.31.3.559.

[109]

C. N. Potts and M. V. Kovalyov, Scheduling with batching: A review,, Fifteenth EURO Summer Institute. Production Scheduling: Deterministic, 120 (2000), 228. doi: 10.1016/S0377-2217(99)00153-8.

[110]

C. N. Potts and V. Wassenhove, Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity,, Journal of Operations Research Society, 43 (1992), 395.

[111]

C. N. Potts and V. Wassenhove, Algorithms for scheduling a single machine to minimize the weighted number of late jobs,, Management Science, 34 (1988), 843. doi: 10.1287/mnsc.34.7.843.

[112]

J. Ren, Y. Zhang, X. Zhang and G. Sun, Approximation algorithms for minimizing the weighted number of tardy jobs on a batch machine,, Combinatorial optimization and applications, (2009), 403. doi: 10.1007/978-3-642-02026-1_38.

[113]

A.H.G. Rinnooy Kan, "Machine Scheduling Problems: Classification, Complexity and Computations,", Nijhoff, (1976).

[114]

G. Rote and G. J. Woeginger, Minimizing the number of tardy jobs on a single machine with batch setup time,, ACTA Cybernetica, 13 (1998), 423.

[115]

R. Sadykov, A hybrid branch and cut for the one dimensional machine scheduling problem,, Lecture notes in Computer Science, 3011 (2004), 409.

[116]

R. Sadykov, A branch and check algorithm for minimizing the weighted number of late jobs on a single machine with release dates,, European Journal of Operational Research, 189 (2008), 1284. doi: 10.1016/j.ejor.2006.06.078.

[117]

S. K. Sahni, Algorithms for scheduling independent tasks,, Journal of Assoc. Comput. Mach, 23 (1976), 116. doi: 10.1145/321921.321934.

[118]

P. Senthilkumar and S. Narayanan, Literature review of single machine scheduling problem with uniform parallel machines,, Intelligent Information Management, 2 (2010), 457. doi: 10.4236/iim.2010.28056.

[119]

D. K. Seo, C. M. Klein and W. Jang, Single machine stochastic scheduling to minimize the expected number of tardy jobs using mathematical programming models,, Computers and Industrial Engineering, 48 (2005), 153. doi: 10.1016/j.cie.2005.01.002.

[120]

M. Sevaux and S. Dauzère-Pérès, Genetic algorithms to minimize the weighted number of late jobs on a single machine,, Meta-heuristics in combinatorial optimization. European Journal of Operational Research, 151 (2003), 296. doi: 10.1016/S0377-2217(02)00827-5.

[121]

D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times,, Discrete Applied Mathematics, 155 (2007), 1643. doi: 10.1016/j.dam.2007.02.003.

[122]

D. Shabtay and G. Steiner, Optimal due date assignment and resource allocation to minimize the weighted number of tardy jobs on a single machine,, Manufacturing and Service Operations Management, 9 (2007), 332. doi: 10.1287/msom.1060.0139.

[123]

D. Shabtay and G. Steiner, Bicriteria models to minimize the total weighted number of tardy jobs with convex controllable processing times and common due date assignment,, Proceedings Multidisciplinary International Conference on Scheduling: Theory and Applications, (2009), 301.

[124]

D. Shabtay and G. Steiner, A bicriteria approach to minimize the total weighted number of tardy jobs with convex controllable processing times and assigning due dates,, Journal of Scheduling, 14 (2011), 455. doi: 10.1007/s10951-010-0208-7.

[125]

A. H. Sharary and N. Zaguia, Minimizing the number of tardy jobs in single machine sequencing,, Discrete Mathematics, 117 (1993), 215. doi: 10.1016/0012-365X(93)90336-R.

[126]

H. M. Soroush, Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem,, European Journal of Operational Research, 181 (2007), 266. doi: 10.1016/j.ejor.2006.05.036.

[127]

G. Steiner and R. Zhang, Minimizing the total weighted number of late jobs with late deliveries in two-level supply chains,, in, (2007), 447. doi: 10.1007/s10951-009-0109-9.

[128]

G. Steiner and R. Zhang, Minimizing the weighted number of late jobs with batch setup times and delivery costs on a single machine,, Multiprocessor Scheduling: Theory and Applications, (2007), 85. doi: 10.5772/5216.

[129]

G. Steiner and R. Zhang, Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains,, Journal of Scheduling, 12 (2009), 565. doi: 10.1007/s10951-009-0109-9.

[130]

G. Steiner, Minimizing the number of tardy jobs with procedence constraints and agreeable due dates,, Models and algorithms for planning and scheduling problems (Loveno di Menaggio, 72 (1997), 167. doi: 10.1016/S0166-218X(96)00043-1.

[131]

L. B. J. M. Sturm, A simple optimality proof of moore's sequencing algorithm,, Management Science, 17 (1970), 116. doi: 10.1287/mnsc.17.1.116.

[132]

G. Tang, A new branch and bound algorithm for minimizing the weighted number of tardy jobs,, Annals of Operations Research, 24 (1990), 225. doi: 10.1007/BF02216825.

[133]

G. L. Vairaktarakis and C. Y. Lee, The single machine scheduling to minimize total tardiness subject to minimum number of tardy jobs,, IIE Transactions, 27 (1995), 250. doi: 10.1080/07408179508936738.

[134]

M. Van der Akker and H. Hoogeveen, Minimizing the number of tardy jobs,, in J. Y.-T. Leung (Ed), (2004).

[135]

F. J. Villarreal and R. L. Bulfin, Scheduling a single machine to minimize the weighted number of tardy jobs,, IE Transactions, 15 (1983), 337. doi: 10.1080/05695558308974657.

[136]

G. Wan and B. P. C. Yen, Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs,, European Journal of Operational Research, 195 (2009), 89. doi: 10.1016/j.ejor.2008.01.029.

[137]

S. Webster and K. R. Baker, Scheduling groups of jobs on a single machine,, Operations Research, 43 (1995), 692. doi: 10.1287/opre.43.4.692.

[138]

W. H. Yang and C. J. Liao, Survey of scheduling research involving setup times,, International Journal of Systems Sciences 30 (1999), 30 (1999), 143. doi: 10.1080/002077299292498.

[139]

B. P. C. Yen and G. Wan, Single machine bicriteria scheduling: A survey,, Industrial Engineering: Theory, 10 (2003), 222.

[140]

W. K. Yeung, C. Oguz and T. C. E. Cheng, Minimizing weighted number of early and tardy jobs with a common due window involving location penalty,, Annals of Operations Research, 108 (2001), 33. doi: 10.1023/A:1016094508744.

[1]

Ming-Jong Yao, Tien-Cheng Hsu. An efficient search algorithm for obtaining the optimal replenishment strategies in multi-stage just-in-time supply chain systems. Journal of Industrial & Management Optimization, 2009, 5 (1) : 11-32. doi: 10.3934/jimo.2009.5.11

[2]

Xingong Zhang. Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2018148

[3]

Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088

[4]

Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial & Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825

[5]

Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial & Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040

[6]

Ganggang Li, Xiwen Lu, Peihai Liu. The coordination of single-machine scheduling with availability constraints and delivery. Journal of Industrial & Management Optimization, 2016, 12 (2) : 757-770. doi: 10.3934/jimo.2016.12.757

[7]

Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058

[8]

Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial & Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613

[9]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

[10]

Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71

[11]

Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial & Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691

[12]

Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial & Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323

[13]

Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071

[14]

Hongwei Li, Yuvraj Gajpal, C. R. Bector. A survey of due-date related single-machine with two-agent scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2019005

[15]

Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017

[16]

Hassen Aydi, Ayman Kachmar. Magnetic vortices for a Ginzburg-Landau type energy with discontinuous constraint. II. Communications on Pure & Applied Analysis, 2009, 8 (3) : 977-998. doi: 10.3934/cpaa.2009.8.977

[17]

Fan Zhang, Guifa Teng, Mengmeng Gao, Shuai Zhang, Jingjing Zhang. Multi-machine and multi-task emergency allocation algorithm based on precedence rules. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1501-1513. doi: 10.3934/dcdss.2019103

[18]

Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial & Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259

[19]

Xianzhao Zhang, Dachuan Xu, Donglei Du, Cuixia Miao. Approximate algorithms for unrelated machine scheduling to minimize makespan. Journal of Industrial & Management Optimization, 2016, 12 (2) : 771-779. doi: 10.3934/jimo.2016.12.771

[20]

Jian Xiong, Yingwu Chen, Zhongbao Zhou. Resilience analysis for project scheduling with renewable resource constraint and uncertain activity durations. Journal of Industrial & Management Optimization, 2016, 12 (2) : 719-737. doi: 10.3934/jimo.2016.12.719

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (20)
  • HTML views (0)
  • Cited by (7)

Other articles
by authors

[Back to Top]