• Previous Article
    A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors
  • JIMO Home
  • This Issue
  • Next Article
    Variance-optimal hedging for target volatility options
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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[12]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[22]

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

[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. Google Scholar

[24]

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

[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. Google Scholar

[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. Google Scholar

[27]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[35]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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). Google Scholar

[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. Google Scholar

[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. Google Scholar

[45]

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

[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. Google Scholar

[47]

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

[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). Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[54]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[58]

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

[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. Google Scholar

[60]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[71]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[79]

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

[80]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[84]

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

[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. Google Scholar

[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. Google Scholar

[87]

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

[88]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[98]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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). Google Scholar

[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. Google Scholar

[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. Google Scholar

[108]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[113]

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

[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. Google Scholar

[115]

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

[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. Google Scholar

[117]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[134]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[139]

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

[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. Google Scholar

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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[12]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[22]

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

[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. Google Scholar

[24]

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

[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. Google Scholar

[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. Google Scholar

[27]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[35]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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). Google Scholar

[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. Google Scholar

[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. Google Scholar

[45]

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

[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. Google Scholar

[47]

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

[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). Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[54]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[58]

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

[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. Google Scholar

[60]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[71]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[79]

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

[80]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[84]

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

[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. Google Scholar

[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. Google Scholar

[87]

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

[88]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[98]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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). Google Scholar

[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. Google Scholar

[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. Google Scholar

[108]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[113]

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

[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. Google Scholar

[115]

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

[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. Google Scholar

[117]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[134]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[139]

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

[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. Google Scholar

[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 (22)
  • HTML views (0)
  • Cited by (7)

Other articles
by authors

[Back to Top]