×

On the flexibility of a decision theory-based heuristic for single machine scheduling. (English) Zbl 1458.90293

Summary: This report extends prior research on the “decision theory” approach for scheduling/sequencing (DTS). Compared to other construction heuristics like priority dispatching (PD) approaches, DTS has the advantage that it is flexible regarding a diverse range of regular and non-regular objectives. Furthermore, multiple decision criteria linearly combined within a single objective function can be addressed. For sequencing a set of jobs on a single machine, DTS estimates the total effect of selecting the next job in the sequence. To this, the completion times for all jobs resulting from this decision need to be estimated. We provide an estimator for job completion times and prove it to be the expected completion time. We also prove that DTS using this estimator provides optimum solutions for a number of single machine scheduling problems. Finally, we provide an extensive computational study comparing DTS to 38 competing PD approaches for a large variety of objectives (31). The results indicate DTS to be a flexible and viable alternative to PD approaches almost independent of specific objectives and problem instance characteristics.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Alidaee, B.; Ramakrishnan, K. R., A computational experiment of COVERT-AU class of rules for single machine tardiness scheduling problem, Comput. Indus. Eng., 30, 2, 201-209, (1996)
[2] Arkin, E. M.; Roundy, R. O., Weighted-tardiness scheduling on parallel machines with proportional weights, Oper. Res., 39, 1, 64-81, (1991) · Zbl 0746.90030
[3] Baker, K. R., Sequencing rules and due-date assignments in a job shop, Manag. Sci., 30, 9, 1093-1104, (1984)
[4] Baker, K. R.; Bertrand, J. W.M., A dynamic priority rule for scheduling against due-dates, J. Oper. Manage., 3, 1, 37-42, (1982)
[5] Baker, K. R.; Trietsch, D., Principles of sequencing and scheduling, (2009), John Wiley Hoboken, N.J. · Zbl 1169.90009
[6] Bock, S.; Pinedo, M. L., A decomposition scheme for single stage scheduling problems, J. Sched., 13, 3, 203-212, (2010) · Zbl 1193.90093
[7] Cai, X., Minimization of agreeably weighted variance in single machine systems, Eur. J. Oper. Res., 85, 3, 576-592, (1995) · Zbl 0912.90172
[8] Carroll, D. C., Heuristic sequencing of single and multiple component jobs, (1965), MIT Cambridge, MA, PhD Dissertation
[9] Chen, C.-L.; Bulfin, R. L., Complexity of single machine, multi-criteria scheduling problems, Eur. J. Oper. Res., 70, 1, 115-125, (1993) · Zbl 0795.90032
[10] Chryssolouris, G.; Pierce, J.; Dicke, K., An approach for allocating manufacturing resources to production tasks, J. Manuf. Syst., 10, 5, 368-382, (1991)
[11] Chryssolouris, G.; Wright, K.; Pierce, J.; Cobb, W., Manufacturing systems operation: dispatch rules versus intelligent control, Rob. Comput. Integr. Manuf., 4, No. 3-4, 531-544, (1988)
[12] Dileepan, P.; Sen, T., Bicriterion static scheduling research for a single machine, Omega, 16, 1, 53-59, (1988)
[13] Gupta, S. K.; Sen, T., Minimizing a quadratic function of job lateness on a single machine, Eng. Costs Prod. Econ., 7, 3, 187-194, (1983)
[14] Haupt, R., A survey of priority rule-based scheduling, OR Spectrum, 11, 1, 3-16, (1989) · Zbl 0658.90047
[15] Hoogeveen, H., Multicriteria scheduling, Eur. J. Oper. Res., 167, 3, 592-623, (2005) · Zbl 1154.90458
[16] Kanet, J. J., Minimizing variation of flow time in single machine systems, Manag. Sci., 27, 12, 1453-1459, (1981) · Zbl 0473.90048
[17] Kanet, J. J.; Hayya, J. C., Priority dispatching with operation due dates in a job shop, J. Oper. Manage., 2, 3, 167-175, (1982)
[18] Kanet, J. J.; Li, X., A weighted modified due date rule for sequencing to minimize weighted tardiness, J. Sched., 7, 4, 261-276, (2004) · Zbl 1154.90465
[19] Kanet, J. J.; Zhou, Z., A decision theory approach to priority dispatching for job shop scheduling, Prod. Oper. Manag., 2, 1, 2-14, (1993)
[20] Koulamas, C. P., The single-machine total tardiness scheduling problem: review and extensions, Eur. J. Oper. Res., 202, 1, 1-7, (2010) · Zbl 1175.90174
[21] Lawler, E. L., Optimal sequencing of a single machine subject to precedence constraints, Manag. Sci., 19, 5, 544-546, (1973) · Zbl 0254.90039
[22] Manna, D. K.; Prasad, V. R., Bounds for the position of the smallest job in completion time variance minimization, Eur. J. Oper. Res., 114, 2, 411-419, (1999) · Zbl 0935.90014
[23] Mebarki, N.; Shahzad, A., Correlation among tardiness-based measures for scheduling using priority dispatching rules, Int. J. Prod. Res., 51, 12, 3688-3697, (2013)
[24] Merten, A. G.; Muller, M. E., Variance minimization in single machine sequencing problems, Manag. Sci., 18, 9, 518-528, (1972) · Zbl 0254.90040
[25] Mönch, L.; Balasubramanian, H.; Fowler, J. W.; Pfund, M. E., Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times, Comput. Oper. Res., 32, 11, 2731-2750, (2005) · Zbl 1071.90019
[26] Moore, J. M., An n job, one machine sequencing algorithm for minimizing the number of late jobs, Manag. Sci., 15, 1, 102-109, (1968) · Zbl 0164.20002
[27] Morton, T. E.; Pentico, D. W., Heuristic scheduling systems: with applications to production systems and project management, (1993), Wiley New York, NY
[28] Nagar, A.; Haddock, J.; Heragu, S., Multiple and bicriteria scheduling: a literature survey, Eur. J. Oper. Res., 81, 1, 88-104, (1995) · Zbl 0913.90178
[29] Nessah, R.; Chu, C., A lower bound for weighted completion time variance, Eur. J. Oper. Res., 207, 3, 1221-1226, (2010) · Zbl 1206.90046
[30] Ow, P. S.; Morton, T. E., The single machine early/tardy problem, Manag. Sci., 35, 2, 177-191, (1989) · Zbl 0666.90043
[31] Pinedo, M. L., Planning and scheduling in manufacturing and services, (2009), Springer Dordrecht · Zbl 1175.90188
[32] Rachamadugu, R. M.V.; Morton, T. E., Myopic heuristics for the weighted tardiness problem on identical parallel machines, (1983), Report CMU-R I-TR-83-17
[33] Sabuncuoglu, I.; Bayiz, M., Job shop scheduling with beam search, Eur. J. Oper. Res., 118, 2, 390-412, (1999) · Zbl 0940.90037
[34] Schaller, J. E., Minimizing the sum of squares lateness on a single machine, Eur. J. Oper. Res., 143, 1, 64-79, (2002) · Zbl 1073.90515
[35] Sen, T.; Dileepan, P.; Lind, M. R., Minimizing a weighted quadratic function of job lateness in the single machine system, Int. J. Prod. Econ., 42, 3, 237-243, (1995)
[36] Sen, T.; Gupta, S. K., A branch-and-bound procedure to solve a bicriterion scheduling problem, IIE Trans., 15, 1, 84-88, (1983)
[37] Sridharan, S. V.; Zhou, Z., A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problems, Eur. J. Oper. Res., 94, 2, 292-301, (1996) · Zbl 0953.90526
[38] Sridharan, S. V.; Zhou, Z., Dynamic non-preemptive single machine scheduling, Comput. Oper. Res., 23, 12, 1183-1190, (1996) · Zbl 0876.90059
[39] Srinivasan, V., A hybrid algorithm for the one machine sequencing problem to minimize total tardiness, Nav. Res. Logist., 18, 3, 317-327, (1971) · Zbl 0229.90029
[40] Srirangacharyulu, B.; Srinivasan, G., Completion time variance minimization in single machine and multi-machine systems, Comput. Oper. Res., 37, 1, 62-71, (2010) · Zbl 1171.90408
[41] Valente, J. M.S., Heuristics for the single machine scheduling problem with early and quadratic tardy penalties, Eur. J. Ind. Eng., 1, 4, 431, (2007)
[42] Valente, J. M.S., Beam search heuristics for quadratic earliness and tardiness scheduling, J. Oper. Res. Soc., 61, 4, 620-631, (2010)
[43] Valente, J. M.S.; Alves, R. A.F. S., Improved heuristics for the early/tardy scheduling problem with no idle time, Comput. Oper. Res., 32, 3, 557-569, (2005) · Zbl 1061.90050
[44] Valente, J. M.S.; Alves, R. A.F. S., Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups, Comput. Oper. Res., 35, 7, 2388-2405, (2008) · Zbl 1177.90186
[45] Valente, J. M.S.; Schaller, J. E., Dispatching heuristics for the single machine weighted quadratic tardiness scheduling problem, Comput. Oper. Res., 39, 9, 2223-2231, (2012) · Zbl 1251.90195
[46] van Wassenhove, L. N.; Gelders, L. F., Four solution techniques for a general one machine scheduling problem, Eur. J. Oper. Res., 2, 4, 281-290, (1978) · Zbl 0378.90044
[47] Vepsalainen, A. P.J.; Morton, T. E., Priority rules for job shops with weighted tardiness costs, Manag. Sci., 33, 8, 1035-1047, (1987)
[48] Vila, M.; Pereira, J., Exact and heuristic procedures for single machine scheduling with quadratic earliness and tardiness penalties, Comput. Oper. Res., 40, 7, 1819-1828, (2013) · Zbl 1348.90319
[49] Wemmerlöv, U.; Hyer, N. L., Cellular manufacturing in the U.S. industry: a survey of users, Int. J. Prod. Res., 27, 9, 1511-1530, (1989)
[50] Wilkerson, L. J.; Irwin, J. D., An improved method for scheduling independent tasks: A I I E transactions, AIIE Trans., 3, 3, 239-245, (1971)
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.