• 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 and 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-17. 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-15. 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, 1990). Discrete Applied Mathematics, 47 (1993), 87-107. 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-239. 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-1032. 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-1919. 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-664.

[8]

K. R. Baker and G. D. Scudder, Scheduling with earliness and tardiness penalties: A review, Operations Research, 38 (1990), 22-36. 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-1288.

[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-252. 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-180. doi: 10.1016/S0167-6377(98)00045-5.

[12]

P. Baptiste, Batching identical jobs, Mathematical Methods of Operations Research, 52 (2000), 355-367. 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-127. 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-264. 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-47. 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-11. 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-107.

[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-126. 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-8. 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-165. 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-54. 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 problemshttp://www.informatik.uni-osnabrueck.de/knust/class/.

[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-404. doi: 10.1137/0207031.

[24]

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

[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-230. 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-360. 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-125.

[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-229. 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-242. 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-13. 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-166. 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-282. 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-281. 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-87. doi: 10.1007/s10951-006-5595-4.

[35]

R. W. Conway, W. L. Maxwell and L. W. Miller, "Theory of Scheduling," Addison-Wesley, Reading, Mass.-London-Don Mills, Ont., 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-177. 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-213. 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-984. 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-142. 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-288. 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-463. 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, Utrecht University Technical Report. UU-CS-054 (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-524.

[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-230. 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, No. 51, Dept of Operations Research, Cornell University, Ithaca, N.Y., 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-400. 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, England, 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., Freeman, San Francisco, 1979.

[49]

M. R. Garey and D. S. Johnson, Scheduling tasks with nonuniform deadlines on two processors, Journal of ACM 23 (1976), 461-467. 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-326. 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-216. 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 (4) (2003), 566-584. 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-64. 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-1719. 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-86. 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-57. doi: 10.1016/0166-218X(90)90093-R.

[58]

H. Hoogeveen, Multicriteria scheduling, European Journal of Operational Research, 167 (2005), 592-623. 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-197. 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-164.

[62]

Y. Huo, J. Y. T. Leung and H. Zhao, Complexity of two-dual criteria scheduling problems, Operations Research Letters, 35 (2007), 211-220. 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-134. 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-434. 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-106. 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-530. 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-190. 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-560. 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-274.

[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-327.

[71]

R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pp. 85-103. Plenum, New York, 1972.

[72]

H. Kise and T. Ibaraki, On balut's algorithm and np-completeness for a chance-constrained scheduling problem, Management Science, 29 (1983), 384-388. 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-126. 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-556. 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-99.

[76]

S. Kravchenko and F. Werner, Parallel machine problems with equal processing times: A survey, J. Sched. 14 (2011), 435-444. 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-781. 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-84. 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-33.

[80]

E. L. Lawler, Scheduling a single machine to minimize the number of late jobs, Report CSD-83-139, EECS Dept., University of California, Berkeley, 1983.

[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-133. 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-106. 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, Handbooks in Operations Research and Management Science, 4, North-Holland, Amsterdam, 1993,445-522.

[84]

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

[85]

D. Lei, Multi-objective production scheduling: A survey, International Journal of Advance Manufacturing Technology, 43 (2009), 926-938. 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-275. doi: 10.1016/0377-2217(80)90111-3.

[87]

J. K. Lenstra, "Production Scheduling," Mathematisch Centrum, Amsterdam, 1977.

[88]

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

[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-219. 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-509. 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-751. 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-193. 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, Communication, Control and Management, 3 (2008),277-280. 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-211. 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-744. 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-56. 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-1001.

[98]

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

[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-498.

[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-2919. 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-804. 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-109. 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-104. 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-479. 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-796. 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-603. doi: 10.1016/S0377-2217(02)00438-1.

[108]

M. Pinedo, stochastic scheduling with release dates and due dates, Operations Research, 31 (1983), 559-572. 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, Stochastic and Fuzzy Approaches (Saint Vincent, 1997). European Journal of Operational Research, 120 (2000), 228-249. 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-406.

[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-858. 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, Springer, Berlin, 2009, 403-410. doi: 10.1007/978-3-642-02026-1_38.

[113]

A.H.G. Rinnooy Kan, "Machine Scheduling Problems: Classification, Complexity and Computations," Nijhoff, The Hague, 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-429.

[115]

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

[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-1304. 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-127. 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-474. 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-161. 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-306. 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-1666. 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-350. 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-310.

[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-469. 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-223. 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-287. 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 "Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Application," Paris, France, 2007, 447-454. 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, Itech Education and Publishing, Vienna, 2007, 85-98. 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-574. 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, 1993). Discrete Applied Mathematics, 72 (1997), 167-177. 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-118. 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-232. 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-256. doi: 10.1080/07408179508936738.

[134]

M. Van der Akker and H. Hoogeveen, Minimizing the number of tardy jobs, in J. Y.-T. Leung (Ed), Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Boca Raton: Chapman and Hall/CRC, 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-343. 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-97. 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-703. 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), 143-155. doi: 10.1080/002077299292498.

[139]

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

[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-54. 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-17. 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-15. 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, 1990). Discrete Applied Mathematics, 47 (1993), 87-107. 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-239. 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-1032. 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-1919. 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-664.

[8]

K. R. Baker and G. D. Scudder, Scheduling with earliness and tardiness penalties: A review, Operations Research, 38 (1990), 22-36. 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-1288.

[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-252. 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-180. doi: 10.1016/S0167-6377(98)00045-5.

[12]

P. Baptiste, Batching identical jobs, Mathematical Methods of Operations Research, 52 (2000), 355-367. 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-127. 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-264. 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-47. 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-11. 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-107.

[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-126. 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-8. 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-165. 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-54. 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 problemshttp://www.informatik.uni-osnabrueck.de/knust/class/.

[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-404. doi: 10.1137/0207031.

[24]

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

[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-230. 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-360. 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-125.

[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-229. 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-242. 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-13. 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-166. 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-282. 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-281. 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-87. doi: 10.1007/s10951-006-5595-4.

[35]

R. W. Conway, W. L. Maxwell and L. W. Miller, "Theory of Scheduling," Addison-Wesley, Reading, Mass.-London-Don Mills, Ont., 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-177. 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-213. 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-984. 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-142. 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-288. 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-463. 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, Utrecht University Technical Report. UU-CS-054 (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-524.

[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-230. 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, No. 51, Dept of Operations Research, Cornell University, Ithaca, N.Y., 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-400. 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, England, 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., Freeman, San Francisco, 1979.

[49]

M. R. Garey and D. S. Johnson, Scheduling tasks with nonuniform deadlines on two processors, Journal of ACM 23 (1976), 461-467. 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-326. 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-216. 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 (4) (2003), 566-584. 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-64. 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-1719. 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-86. 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-57. doi: 10.1016/0166-218X(90)90093-R.

[58]

H. Hoogeveen, Multicriteria scheduling, European Journal of Operational Research, 167 (2005), 592-623. 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-197. 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-164.

[62]

Y. Huo, J. Y. T. Leung and H. Zhao, Complexity of two-dual criteria scheduling problems, Operations Research Letters, 35 (2007), 211-220. 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-134. 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-434. 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-106. 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-530. 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-190. 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-560. 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-274.

[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-327.

[71]

R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pp. 85-103. Plenum, New York, 1972.

[72]

H. Kise and T. Ibaraki, On balut's algorithm and np-completeness for a chance-constrained scheduling problem, Management Science, 29 (1983), 384-388. 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-126. 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-556. 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-99.

[76]

S. Kravchenko and F. Werner, Parallel machine problems with equal processing times: A survey, J. Sched. 14 (2011), 435-444. 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-781. 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-84. 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-33.

[80]

E. L. Lawler, Scheduling a single machine to minimize the number of late jobs, Report CSD-83-139, EECS Dept., University of California, Berkeley, 1983.

[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-133. 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-106. 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, Handbooks in Operations Research and Management Science, 4, North-Holland, Amsterdam, 1993,445-522.

[84]

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

[85]

D. Lei, Multi-objective production scheduling: A survey, International Journal of Advance Manufacturing Technology, 43 (2009), 926-938. 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-275. doi: 10.1016/0377-2217(80)90111-3.

[87]

J. K. Lenstra, "Production Scheduling," Mathematisch Centrum, Amsterdam, 1977.

[88]

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

[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-219. 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-509. 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-751. 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-193. 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, Communication, Control and Management, 3 (2008),277-280. 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-211. 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-744. 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-56. 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-1001.

[98]

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

[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-498.

[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-2919. 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-804. 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-109. 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-104. 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-479. 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-796. 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-603. doi: 10.1016/S0377-2217(02)00438-1.

[108]

M. Pinedo, stochastic scheduling with release dates and due dates, Operations Research, 31 (1983), 559-572. 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, Stochastic and Fuzzy Approaches (Saint Vincent, 1997). European Journal of Operational Research, 120 (2000), 228-249. 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-406.

[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-858. 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, Springer, Berlin, 2009, 403-410. doi: 10.1007/978-3-642-02026-1_38.

[113]

A.H.G. Rinnooy Kan, "Machine Scheduling Problems: Classification, Complexity and Computations," Nijhoff, The Hague, 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-429.

[115]

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

[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-1304. 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-127. 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-474. 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-161. 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-306. 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-1666. 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-350. 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-310.

[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-469. 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-223. 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-287. 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 "Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Application," Paris, France, 2007, 447-454. 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, Itech Education and Publishing, Vienna, 2007, 85-98. 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-574. 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, 1993). Discrete Applied Mathematics, 72 (1997), 167-177. 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-118. 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-232. 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-256. doi: 10.1080/07408179508936738.

[134]

M. Van der Akker and H. Hoogeveen, Minimizing the number of tardy jobs, in J. Y.-T. Leung (Ed), Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Boca Raton: Chapman and Hall/CRC, 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-343. 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-97. 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-703. 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), 143-155. doi: 10.1080/002077299292498.

[139]

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

[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-54. doi: 10.1023/A:1016094508744.

[1]

Alireza Goli, Taha Keshavarz. Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021124

[2]

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 and Management Optimization, 2009, 5 (1) : 11-32. doi: 10.3934/jimo.2009.5.11

[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 and Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088

[4]

Xingong Zhang. Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon. Journal of Industrial and Management Optimization, 2020, 16 (1) : 231-244. doi: 10.3934/jimo.2018148

[5]

Reza Alizadeh Foroutan, Javad Rezaeian, Milad Shafipour. Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021190

[6]

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

[7]

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 and Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040

[8]

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

[9]

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

[10]

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

[11]

Hongwei Li, Yuvraj Gajpal, C. R. Bector. A survey of due-date related single-machine with two-agent scheduling problem. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1329-1347. doi: 10.3934/jimo.2019005

[12]

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 and Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269

[13]

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

[14]

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 and Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691

[15]

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 and Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323

[16]

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 and Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071

[17]

Shuen Guo, Zhichao Geng, Jinjiang Yuan. Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021192

[18]

Binghai Zhou, Yuanrui Lei, Shi Zong. Lagrangian relaxation algorithm for the truck scheduling problem with products time window constraint in multi-door cross-dock. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021151

[19]

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

[20]

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

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (397)
  • HTML views (0)
  • Cited by (16)

Other articles
by authors

[Back to Top]