×

A survey of the state-of-the-art of common due date assignment and scheduling research. (English) Zbl 1009.90054

Summary: We aim at providing a unified framework of the common due date assignment and scheduling problems in the deterministic case by surveying the literature concerning the models involving single machine and parallel machines. The problems with due date determination have received considerable attention in the last 15 years due to the introduction of new methods of inventory management such as just-in-time concepts. The common due date model corresponds, for instance, to an assembly system in which the components of the product should be ready at the same time, or to a shop where several jobs constitute a single customer’s order. In the problems under consideration, the objective is to find an optimal value of the common due date and the related optimal schedule in order to optimize a given criterion based on the due date and the completion times of jobs. The results on the algorithms and complexity of the common due date assignment and scheduling problems are summarized.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adamopoulos, G. I.; Pappis, C. P., Scheduling under a common due-date on parallel unrelated machines, European Journal of Operational Research, 105, 494-501 (1998) · Zbl 0955.90030
[2] Alidaee, B.; Ahmadian, A., Two parallel machine sequencing problems involving controllable job processing times, European Journal of Operational Research, 70, 335-341 (1993) · Zbl 0791.90028
[3] Alidaee, B.; Panwalkar, S. S., Single stage minimum absolute lateness problem with a common due date on non-identical machines, Journal of the Operational Research Society, 44, 29-36 (1993) · Zbl 0772.90050
[4] Azizoglu, M.; Webster, S., Scheduling about an unrestricted common due window with arbitrary earliness/tardiness penalty rates, IIE Transactions, 29, 1001-1006 (1997)
[5] Azizoglu, M.; Webster, S., Scheduling job families about an unrestricted common due date on a single machine, International Journal of Production Research, 35, 1321-1330 (1997) · Zbl 0942.90547
[6] Bagchi, U.; Chang, Y. L.; Sullivan, R. S., Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date, Naval Research Logistics, 34, 739-751 (1987) · Zbl 0657.90052
[7] Bagchi, U.; Sullivan, R. S.; Chang, Y. L., Minimizing mean absolute deviation of completion times about a common due date, Naval Research Logistics, 33, 227-240 (1986) · Zbl 0599.90049
[8] Bagchi, U.; Sullivan, R. S.; Chang, Y. L., Minimizing mean squared deviation of completion times about a common due date, Management Science, 33, 894-906 (1987) · Zbl 0636.90049
[9] Baker, K. R.; Scudder, G. D., On the assignment of optimal due dates, Journal of the Operational Research Society, 40, 93-95 (1989) · Zbl 0674.90052
[10] Baker, K. R.; Scudder, G. D., Sequencing with earliness and tardiness penalties: A review, Operations Research, 38, 22-36 (1990) · Zbl 0699.90052
[11] Bector, C. R.; Gupta, Y. P.; Gupta, M. C., Determination of an optimal common due date and optimal sequence in a single machine job shop, International Journal of Production Research, 26, 613-628 (1988) · Zbl 0644.90047
[12] Biskup, D., Single-machine scheduling with learning considerations, European Journal of Operational Research, 115, 173-178 (1999) · Zbl 0946.90025
[13] Biskup, D.; Cheng, T. C.E., Single-machine scheduling with controllable processing times and earliness, tardiness and completion time penalties, Engineering Optimization, 31, 329-336 (1999)
[14] Biskup, D.; Cheng, T. C.E., Multiple-machine scheduling with earliness, tardiness and completion time penalties, Computers and Operations Research, 26, 45-57 (1999) · Zbl 0957.90056
[15] Biskup, D.; Feldmann, M., Benchmarks for scheduling on a single-machine against restrictive and unrestrictive common due dates, Computers and Operations Research, 28, 787-801 (2001) · Zbl 1003.90020
[16] Biskup, D.; Jahnke, H., Common due date assignment for scheduling on a single machine with jointly reducible processing times, International Journal of Production Economics, 69, 317-322 (2001)
[17] Blazewicz, J.; Ecker, K.; Pesch, E.; Schmidt, G.; Weglarz, J., Scheduling Computer and Manufacturing Processes (1996), Springer: Springer Berlin · Zbl 0911.90201
[18] Blazewicz, J.; Ecker, K.; Schmidt, G.; Weglarz, J., Scheduling in Computer and Manufacturing Systems (1993), Springer: Springer Berlin · Zbl 0767.90033
[20] Brucker, P., Scheduling Algorithms (1998), Springer: Springer Berlin · Zbl 0914.90157
[21] Bruno, J. L.; Coffman, E. G.; Sethi, R., Scheduling independent tasks to reduce mean finishing time, Communications of the ACM, 17, 382-387 (1974) · Zbl 0283.68039
[22] Cai, X., Minimization of agreeably weighted variance in single machine systems, European Journal of Operational Research, 85, 576-592 (1995) · Zbl 0912.90172
[23] Cai, X.; Lum, V. Y.S.; Chan, J. M.T., Scheduling about a common due date with job-dependent asymmetric earliness and tardiness penalties, European Journal of Operational Research, 98, 154-168 (1997) · Zbl 0922.90084
[25] Chen, D.; Li, S.; Tang, G., Single machine scheduling with common due date assignment in a group technology environment, Mathematical and Computer Modelling, 25, 81-90 (1997) · Zbl 0894.90076
[26] Chen, Z.-L., Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs, European Journal of Operational Research, 93, 49-60 (1996) · Zbl 0916.90147
[27] Cheng, T. C.E., A duality approach to optimal due-date determination, Engineering Optimization, 9, 127-130 (1985)
[28] Cheng, T. C.E., An algorithm for the CON due-date determination and sequencing problem, Computers and Operations Research, 14, 537-542 (1987) · Zbl 0634.90030
[29] Cheng, T. C.E., Minimizing the maximum deviation of job completion time about a common due-date, Computers and Mathematics with Applications, 14, 279-283 (1987) · Zbl 0636.90045
[30] Cheng, T. C.E., Optimal common due-date with limited completion time deviation, Computers and Operations Research, 15, 91-96 (1988) · Zbl 0635.90050
[32] Cheng, T. C.E., A heuristic for common due-date assignment and job scheduling on parallel machines, Journal of the Operational Research Society, 40, 1129-1135 (1989) · Zbl 0699.90060
[33] Cheng, T. C.E., A note on a partial search algorithm for the single-machine optimal common due-date assignment and sequencing problem, Computers and Operations Research, 17, 321-324 (1990) · Zbl 0699.90061
[34] Cheng, T. C.E., Common due-date assignment and scheduling for a single processor to minimize the number of tardy jobs, Engineering Optimization, 16, 129-136 (1990)
[35] Cheng, T. C.E., Optimal constant due-date determination and sequencing of \(n\) jobs on a single machine, International Journal of Production Economics, 22, 259-261 (1991)
[36] Cheng, T. C.E.; Chen, Z.-L., Parallel-machine scheduling problems with earliness and tardiness penalties, Journal of the Operational Research Society, 45, 685-695 (1994) · Zbl 0829.90077
[37] Cheng, T. C.E.; Gupta, M. C., Survey of scheduling research involving due date determination decisions, European Journal of Operational Research, 38, 156-166 (1989) · Zbl 0658.90049
[38] Cheng, T. C.E.; Kovalyov, M. Y., Batch scheduling and common due-date assignment on a single machine, Discrete Applied Mathematics, 70, 231-245 (1996) · Zbl 0871.90044
[39] Cheng, T. C.E.; Oguz, C.; Qi, X. D., Due-date assignment and single machine scheduling with compressible processing times, International Journal of Production Economics, 43, 29-35 (1996)
[40] Cheng, T. C.E.; Sin, C. C.S., A state-of-the-art review of parallel-machine scheduling research, European Journal of Operational Research, 47, 271-292 (1990) · Zbl 0707.90053
[41] Conway, R. W., Priority dispatching and job lateness in a job shop, Journal of Industrial Engineering, 16, 228-237 (1965)
[43] Davis, J. S.; Kanet, J. J., Single-machine scheduling with early and tardy completion costs, Naval Research Logistics, 40, 85-101 (1993) · Zbl 0769.90048
[44] De, P.; Ghosh, J. B.; Wells, C. E., A note on the minimization of mean squared deviation of completion times about a common due date, Management Science, 35, 1143-1147 (1989) · Zbl 0683.90039
[45] De, P.; Ghosh, J. B.; Wells, C. E., CON due-date determination and sequencing, Computers and Operations Research, 17, 333-342 (1990) · Zbl 0693.90048
[46] De, P.; Ghosh, J. B.; Wells, C. E., Scheduling about a common due date with earliness and tardiness penalties, Computers and Operations Research, 17, 231-241 (1990) · Zbl 0693.90055
[47] De, P.; Ghosh, J. B.; Wells, C. E., Optimal delivery time quotation and order sequencing, Decision Science, 22, 379-390 (1991)
[48] De, P.; Ghosh, J. B.; Wells, C. E., On the multiple-machine extension to a common due-date assignment and scheduling problem, Journal of the Operational Research Society, 42, 419-422 (1991)
[49] De, P.; Ghosh, J. B.; Wells, C. E., On the minimization of completion time variance with a bicriteria extension, Operations Research, 40, 1148-1155 (1992) · Zbl 0770.90032
[50] De, P.; Ghosh, J. B.; Wells, C. E., On the general solution for a class of early/tardy problems, Computers and Operations Research, 20, 141-149 (1993) · Zbl 0794.90021
[51] De, P.; Ghosh, J. B.; Wells, C. E., Solving a generalized model for CON due date assignment and sequencing, International Journal of Production Economics, 34, 179-185 (1994)
[52] De, P.; Ghosh, J. B.; Wells, C. E., Due-date assignment and early/tardy scheduling on identical parallel machines, Naval Research Logistics, 41, 17-32 (1994) · Zbl 0794.90022
[53] Della Croce, F.; Gupta, J. N.D.; Tadei, R., Minimizing tardy jobs in a flowshop with common due date, European Journal of Operational Research, 120, 375-381 (2000) · Zbl 0949.90040
[54] Dickman, B.; Wilamowsky, Y.; Epstein, S., Optimal common due date with limited completion time, Computers and Operations Research, 18, 125-127 (1991) · Zbl 0716.90052
[55] Dileepan, P., Common due date scheduling problem with separate earliness and tardiness penalties, Computers and Operations Research, 20, 179-181 (1993) · Zbl 0770.90033
[56] Eilon, S.; Chowdhury, I. J., Due dates in job shop scheduling, International Journal of Production Research, 14, 223-237 (1976)
[57] Emmons, H., Scheduling to a common due date on parallel uniform processors, Naval Research Logistics Quarterly, 34, 803-810 (1987) · Zbl 0648.90043
[58] Federgruen, A.; Mosheiov, G., Simultaneous optimization of efficiency and performance balance measures in single-machine scheduling problems, Naval Research Logistics, 40, 951-970 (1993) · Zbl 0801.90060
[59] Federgruen, A.; Mosheiov, G., Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs, Operations Research Letters, 16, 199-208 (1994) · Zbl 0823.90060
[61] Garey, M. R.; Tarian, R. T.; Wilfong, G. T., One-processor scheduling with symmetric earliness and tardiness penalties, Mathematics of Operations Research, 13, 330-348 (1988) · Zbl 0671.90033
[62] Gee, E. S.; Smith, C. H., Selecting allowance policies for improved job shop performance, International Journal of Production Research, 31, 1839-1852 (1993)
[64] Gupta, M. C.; Gupta, Y. P.; Kumar, A., Minimizing flow time variance in a single machine system using genetic algorithms, European Journal of Operational Research, 70, 289-303 (1993) · Zbl 0784.90036
[65] Gupta, S. K.; Kyparisis, J., Single machine scheduling research, OMEGA, 15, 207-227 (1987)
[66] Gupta, Y. P.; Bector, C. R.; Gupta, M. C., Optimal schedule on a single machine using various due date determination methods, Computers in Industry, 15, 245-253 (1990)
[67] Hall, N. G., Scheduling problems with generalized due dates, IIE Transactions, 18, 220-222 (1986)
[68] Hall, N. G., Single- and multiple-processor models for minimizing completion time variance, Naval Research Logistics Quarterly, 33, 49-54 (1986) · Zbl 0599.90057
[69] Hall, N. G.; Kubiak, W.; Sethi, S. P., Earliness-tardiness scheduling problems, II: Deviation of completion times about a restrictive common due date, Operations Research, 39, 847-856 (1991) · Zbl 0762.90037
[70] Hall, N. G.; Posner, M. E., Earliness-tardiness scheduling problems, I: Weighted deviation of completion times about a common due date, Operations Research, 39, 836-846 (1991) · Zbl 0749.90041
[71] Hall, N. G.; Sethi, S. P.; Sriskandarajah, C., On the complexity of generalized due date scheduling problems, European Journal of Operational Research, 51, 100-109 (1991) · Zbl 0742.90043
[72] Hao, Q.; Yang, Z.; Wang, D.; Li, Z., Common due date determination and sequencing using tabu search, Computers and Operations Research, 23, 409-417 (1996) · Zbl 0849.90078
[73] Hardy, G. H.; Littlewood, J. E.; Polya, G., Inequalities (1934), Cambridge University Press: Cambridge University Press New York · JFM 60.0169.01
[74] Herrmann, J. W.; Lee, C.-Y., On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date, European Journal of Operational Research, 70, 272-288 (1993) · Zbl 0842.90060
[76] Hoogeveen, J. A.; Oosterhout, H.; van de Velde, S. L., New lower and upper bounds for scheduling around a small common due date, Operations Research, 42, 102-110 (1994) · Zbl 0798.90085
[77] Hoogeveen, J. A.; van de Velde, S. L., Scheduling around a small common due date, European Journal of Operational Research, 55, 237-242 (1991) · Zbl 0755.90044
[78] Hoogeveen, J. A.; van de Velde, S. L., Earliness-tardiness scheduling around almost equal due date, INFORMS Journal on Computing, 9, 92-99 (1997) · Zbl 0889.90089
[80] James, R. J.W., Using tabu search to solve the common due date early/tardy machine scheduling problem, Computers and Operations Research, 24, 199-208 (1997) · Zbl 0889.90090
[81] Jozefowska, J.; Jurisch, B.; Kubiak, W., Scheduling shops to minimize the weighted number of late jobs, Operations Research Letters, 16, 277-283 (1994) · Zbl 0823.90061
[82] Jurisch, B.; Kubiak, W.; Jozefowska, J., Algorithms for minclique scheduling problems, Discrete Applied Mathematics, 72, 115-139 (1997) · Zbl 0872.90048
[83] Kahlbacher, H. G., SWEAT - a program for a scheduling problem with earliness and tardiness penalties, European Journal of Operational Research, 43, 111-112 (1989)
[84] Kahlbacher, H. G., Scheduling with monotonous earliness and tardiness penalties, European Journal of Operational Research, 64, 258-277 (1993) · Zbl 0776.90036
[85] Kahlbacher, H. G.; Cheng, T. C.E., Parallel machine scheduling to minimize costs for earliness and number of tardy jobs, Discrete Applied Mathematics, 47, 139-164 (1993) · Zbl 0816.90084
[86] Kanet, J. J., Minimizing the average deviation of job completion times about a common due date, Naval Research Logistics Quarterly, 28, 643-651 (1981) · Zbl 0548.90037
[87] Karacapilidis, N. I.; Pappis, C. P., Form similarities of the CON and SLK due date determination methods, Journal of the Operational Research Society, 46, 762-770 (1995) · Zbl 0832.90056
[88] Karacapilidis, N. I.; Pappis, C. P., Optimization algorithms for a class of single machine scheduling problems using due date determination methods, Yugoslavian Journal of Operations Research, 5, 289-297 (1995) · Zbl 0860.90072
[89] Kawaguchi, T.; Kyan, S., Deterministic scheduling in computer systems: A survey, Journal of the Operational Research Society of Japan, 31, 190-217 (1988) · Zbl 0644.68048
[90] Koulamas, C., The total tardiness problem: Review and extensions, Operations Research, 42, 1025-1041 (1994) · Zbl 0824.90083
[91] Kovalyov, M. Y., Batch scheduling and common due date assignment problem: An NP-hard case, Discrete Applied Mathematics, 80, 251-254 (1997) · Zbl 0894.68011
[92] Kovalyov, M. Y.; Kubiak, W., A fully polynomial approximation scheme for the weighted earliness-tardiness problem, Operations Research, 47, 757-761 (1999) · Zbl 0976.90042
[93] Kramer, F.-J.; Lee, C.-Y., Common due-window scheduling, Production and Operations Management, 2, 262-275 (1993)
[94] Kubiak, W., Completion time variance minimization on a single machine is difficult, Operations Research Letters, 14, 49-59 (1993) · Zbl 0794.90024
[95] Kubiak, W., New results on the completion time variance minimization, Discrete Applied Mathematics, 58, 157-168 (1995) · Zbl 0833.90070
[96] Kubiak, W.; Lou, S.; Sethi, R., Equivalence of mean flow time problems and mean absolute deviation problems, Operations Research Letters, 9, 371-374 (1990) · Zbl 0825.90553
[97] Lakshminarayan, S.; Lakshmanan, R.; Papineau, R. L.; Rochette, R., Optimal single-machine scheduling with earliness and tardiness penalties, Operations Research, 26, 1079-1082 (1978) · Zbl 0413.90031
[99] Lawler, E. L.; Moore, J. M., A functional equation and its application to resource allocations and sequencing problems, Management Science, 16, 77-84 (1969) · Zbl 0184.23303
[100] Lawrence, S. R., Estimating flowtimes and setting due-dates in complex production systems, IIE Transactions, 27, 657-668 (1995)
[101] Lee, C.-Y.; Danusaputro, S. L.; Lin, C.-S., Minimizing weighted number of tardy jobs and weighted earliness-tardiness penalties about a common due date, Computers and Operations Research, 18, 379-389 (1991) · Zbl 0717.90037
[102] Lee, C.-Y.; Kim, S. J., Parallel genetic algorithms for the earliness tardiness job scheduling problem with general penalty weights, Computers and Industrial Engineering, 28, 231-243 (1995)
[103] Li, C.-L.; Cheng, T. C.E., The parallel machine min-max weighted absolute lateness scheduling problem, Naval Research Logistics, 41, 33-46 (1994) · Zbl 0808.90082
[104] Liman, S. D.; Panwalkar, S. S.; Thongmee, S., Determination of common due window location in a single machine scheduling problem, European Journal of Operational Research, 93, 68-74 (1996) · Zbl 0912.90176
[105] Liman, S. D.; Panwalkar, S. S.; Thongmee, S., Common due window size and location determination in a single machine scheduling problem, Journal of the Operational Research Society, 49, 1007-1010 (1998) · Zbl 1140.90405
[106] Merten, A. G.; Muller, M. E., Variance minimization in a single machine sequencing problems, Management Science, 18, 518-528 (1972) · Zbl 0254.90040
[108] Morton, T. E.; Pentico, D. W., Heuristic Scheduling Systems (1993), Wiley: Wiley New York
[109] Panwalkar, S. S.; Rajagopalan, R., Single machine sequencing with controllable processing times, European Journal of Operational Research, 59, 298-302 (1992) · Zbl 0760.90058
[110] Panwalkar, S. S.; Smith, M. L.; Seidmann, A., Common due date assignment to minimize total penalty for the one machine scheduling problem, Operations Research, 30, 391-399 (1982) · Zbl 0481.90042
[111] Pappis, C. P.; Adamopoulos, G. I., Scheduling under the due date criterion with varying penalties for lateness, Yugoslavian Journal of Operations Research, 3, 189-198 (1993) · Zbl 0804.90075
[112] Philipoom, P. R.; Wiegmann, L.; Rees, L. P., Cost-based due-date assignment with the use of classical and neural-network approaches, Naval Research Logistics, 44, 21-46 (1997) · Zbl 0882.90073
[113] Pinedo, M. L., Scheduling: Theory, Algorithms, and Systems (1995), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1145.90393
[114] Quaddus, M. A., A generalized model of optimal due-date assignment by linear programming, Journal of the Operational Research Society, 38, 353-359 (1987) · Zbl 0608.90045
[115] Raghavachari, M., A V-shape property of optimal schedule of jobs about a common due date, European Journal of Operational Research, 23, 401-402 (1986) · Zbl 0584.90043
[116] Raghavachari, M., Scheduling problems with non-regular penalty functions – a review, Operations Research, 25, 144-164 (1988) · Zbl 0649.90065
[117] Ramasesh, R., Dynamic job shop scheduling: A survey of simulation research, OMEGA, 18, 43-57 (1990)
[118] Roman, D. B.; Valle, A. G., Dynamic assignation of due-dates in an assembly shop based in simulation, International Journal of Production Research, 34, 1539-1554 (1996) · Zbl 0927.90039
[119] Sarper, H., Minimizing the sum of absolute deviations about a common due date for the two-machine flow shop problem, Applied Mathematics Modelling, 19, 153-161 (1995) · Zbl 0829.90075
[120] Seidmann, A.; Panwalkar, S. S.; Smith, M. L., Optimal assignment of due-dates for a single processor scheduling problem, International Journal of Production Research, 19, 393-399 (1981) · Zbl 0481.90042
[121] Sen, T.; Gupta, S. K., A state-of-art survey of static scheduling research involving due dates, OMEGA, 12, 63-76 (1984)
[122] Smith, C. H.; Minor, E. D.; Wen, H. J., Regression-based due date assignment rules for improved assembly shop performance, International Journal of Production Research, 33, 2375-2385 (1995) · Zbl 0909.90182
[123] Sundararaghavan, P. S.; Ahmed, M. U., Minimizing the sum of absolute lateness in single-machine and multimachine scheduling, Naval Research Logistics Quarterly, 31, 325-333 (1984) · Zbl 0544.90052
[124] Szwarc, W., Single-machine scheduling to minimize absolute deviation of completion times from a common due date, Naval Research Logistics, 36, 663-673 (1989) · Zbl 0674.90049
[125] Szwarc, W., The weighted common due date single machine scheduling problem revisited, Computers and Operations Research, 23, 255-262 (1996) · Zbl 0855.90072
[126] Tanaev, V. S.; Gordon, V. S.; Shafransky, Y. M., Scheduling Theory: Single-Stage Systems (1994), Kluwer: Kluwer Dordrecht · Zbl 0827.90079
[127] Tanaev, V. S.; Sotskov, Y. N.; Strusevich, V. A., Scheduling Theory: Multi-Stage Systems (1994), Kluwer: Kluwer Dordrecht · Zbl 0925.90224
[128] Tsai, C.-H.; Chang, G.-T.; Li, R.-K., Integrating order release control with due-date assignment rules, International Journal of Production Research, 35, 3379-3392 (1997) · Zbl 0943.90512
[130] Ventura, J. A.; Weng, M. X., An improved dynamic programming algorithm for the single-machine mean absolute deviation problem with a restrictive common due date, Operations Research Letters, 17, 149-152 (1995) · Zbl 0842.90067
[131] Vig, M. M.; Dooley, K. J., Dynamic rules for due date assignments, International Journal of Production Research, 29, 1361-1377 (1991)
[132] Vig, M. M.; Dooley, K. J., Mixing static and dynamic flowtime estimates for due-date assignment, Journal of Operations Management, 11, 67-79 (1993)
[133] Weeks, J. K.; Fryer, J. S., A methodology for assigning minimum cost due-dates, Management Science, 23, 872-881 (1979)
[134] Webster, S. T., The complexity of scheduling job families about a common due date, Operations Research Letters, 20, 65-74 (1997) · Zbl 0890.90111
[135] Weng, M. X.; Ventura, J. A., Scheduling about a large common due date with tolerance to minimize mean absolute deviation of completion times, Naval Research Logistics Quarterly, 41, 843-851 (1994) · Zbl 0827.90080
[136] Wilamowsky, Y.; Epstein, S.; Dickman, B., Optimal common due-date completion time tolerance, Computers and Operations Research, 23, 1203-1210 (1996) · Zbl 0873.90057
[137] Yeung, W. K.; Oguz, C.; Cheng, T. C.E., Single-machine scheduling with a common due window, Computers and Operations Research, 28, 157-175 (2001) · Zbl 0990.90050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.