\`x^2+y_1+z_12^34\`
Advanced Search
This issue Previous Article Next Article
Article Contents
Article Contents
2014, Volume 10, Issue 1: 219-241. Doi: 10.3934/jimo.2014.10.219
This issue Previous Article Variance-optimal hedging for target volatility options Next Article A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors

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

  • 1.

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

  • 2.

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

Received:  January 2012
Revised:  March 2013
Published:  January 2014
Abstract / Introduction Related Papers Cited by
    Abstract
  • 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.
    Mathematics Subject Classification: Primary: 90Bxx, 90Cxx; Secondary: 90C59, 68W25, 62L20, 90B35, 90B36, 68T20, 53C35.

    Citation:
    shu

    \begin{equation} \\ \end{equation}
    • Related Papers
  • Cited by
  • 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 problems, http://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.

    • Access History
  • 加载中
PDF
XML
Export Citation
SHARE
Email to a Friend

Article Metrics

HTML views() PDF downloads(453) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return
    Site map Copyright © 2024 American Institute of Mathematical Sciences