The stochastic single machine scheduling problem with earliness and tardiness costs. (English) Zbl 0809.90083
Summary: This paper studies the static single machine scheduling problem with earliness and tardiness costs where job processing times are random variables and due dates are distinct and deterministic. The objective is to identify an optimal sequence which minimizes the total expected earliness plus tardiness cost. A case where processing times are normally distributed is fully explored. We demonstrate that variations in processing times increase cost and affect sequencing decisions. Three heuristics for finding an optimal sequence are proposed. The illustrative example and computational results indicate that optimal sequences and their expected costs are significantly different from those provided by the classical deterministic single machine models. Furthermore, our computational experiments show that two of the proposed heuristics perform well in identifying optimal sequences.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
static single machine scheduling; earliness and tardiness costs; job processing times; heuristicsReferences:
| [1] | Abdul-Razaq, T.; Potts, C., Dynamic programming state-space relaxation for single machine scheduling, Journal of the Operational Research Society, 39, 141-152 (1988) · Zbl 0655.90034 |
| [2] | Ahmadi, R.; Bagchi, U., Single machine scheduling to minimize earliness subject to deadlines, (Working Paper 86/86-4-17 (1986), Department of Management, University of Texas: Department of Management, University of Texas Austin, TX) |
| [3] | Ahmadi, R.; Bagchi, U., Just-in-time scheduling in single machine systems, (Working paper 85/86-4-21 (1986), Department of Management, University of Texas: Department of Management, University of Texas Austin, TX) |
| [4] | Bagchi, U., Scheduling to minimize earliness and tardiness penalties with common due date (1985), Department of Management, University of Texas: Department of Management, University of Texas Austin, TX, Working Paper |
| [5] | Bagchi, U.; Chang, Y.; Sullivan, R., Minimizing absolute and squared deviations of completion times with different earliness and tardiness penalties and a common due date, Naval Research Logistics Quarterly, 34, 739-751 (1987) · Zbl 0657.90052 |
| [6] | Bagchi, U.; Sullivan, R.; Chang, Y., Minimizing mean absolute deviation of completion times about a common due date, Naval Research Logistics Quarterly, 33, 227-240 (1986) · Zbl 0599.90049 |
| [7] | Baker, K. R., Introduction to Sequencing and Scheduling (1974), Wiley: Wiley New York |
| [8] | Baker, K. R.; Chadowitz, A., Algorithms for minimizing earliness and tardiness penalties with a common due date, (Working Paper No. 240 (1989), Amos Tuck School of Business Administration, Dartmouth College: Amos Tuck School of Business Administration, Dartmouth College Hanover, NH) |
| [9] | Baker, K. R.; Schrage, L., Finding an optimal sequence by dynamic programming: An extension to precedence related tasks, Operations Research, 26, 111-120 (1978) · Zbl 0376.90055 |
| [10] | Baker, K.; Scudder, G., On the assignment of optimal due dates, Journal of the Operational Research Society, 40, 93-95 (1989) · Zbl 0674.90052 |
| [11] | Baker, K. R.; Scudder, G. D., Sequencing with earliness and tardiness penalties: A review, Operations Research, 38, 22-36 (1990) · Zbl 0699.90052 |
| [12] | Balut, S. J., Scheduling to minimize the number of late jobs when set-up and processing times are uncertain, Management Science, 19, 1283-1288 (1973) · Zbl 0261.90025 |
| [13] | Banerjee, B. P., Single machine scheduling with random execution times, Operations Research, 13, 358-364 (1965) |
| [14] | Bertrand, J. W.M., The use of workload information to control job lateness in controlled and uncontrolled release production systems, Journal of Operations Management, 3, 79-92 (1983) |
| [15] | Blau, R. A., \(N\)-job, one machine sequencing problems under uncertainty, Management Science, 20, 101-109 (1973) · Zbl 0304.90060 |
| [16] | Boxma, O. J.; Forst, F. G., Minimizing the expected weighted number of tardy jobs in stochastic flow shops, Operations Research Letters, 5, 119-126 (1986) · Zbl 0633.90028 |
| [17] | Chakravarthy, S., A single machine scheduling problem with random processing times, Naval Research Logistics Quarterly, 33, 391-397 (1986) · Zbl 0598.90051 |
| [18] | Cheng, T. C.E., Optimal assignment of slack due-dates and sequencing of jobs with random processing times on a single machine, European Journal of Operational research, 51, 348-353 (1991) · Zbl 0745.90035 |
| [19] | Coleman, B. J., A simple model for optimization the single machine early/tardy problem with sequence-dependent set-ups, Productions and Operations Management, 1, 225-228 (1992) |
| [20] | Conway, R. W.; Maxwell, W. L.; Miller, L. W., Theory of Scheduling (1967), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 1058.90500 |
| [21] | Crabill, T. B.; Maxwell, W. L., Single machine sequencing with random processing times and random due-dates, Naval Research Logistic Quarterly, 19, 549-554 (1969) · Zbl 0194.19905 |
| [22] | Davis, J., and Kanet, J., “Single machine scheduling with a nonregular convex performance measure”, Naval Research Logistics (forthcoming).; Davis, J., and Kanet, J., “Single machine scheduling with a nonregular convex performance measure”, Naval Research Logistics (forthcoming). · Zbl 0769.90048 |
| [23] | De, P.; Ghosh, J. B.; Wells, C. E., On the minimization of the weighted number of tardy jobs with random processing times and deadline, Computers & Operations Research, 18, 457-463 (1991) · Zbl 0744.90040 |
| [24] | Eilon, S.; Chowdhury, I. G., Minimizing waiting time variance in the single machine problem, Management Science, 23, 567-575 (1977) · Zbl 0362.90051 |
| [25] | Elmaghraby, S. E., The one-machine sequencing problem with delay costs, Journal of Industrial Engineering, 19, 105-108 (1968) |
| [26] | Emmons, H., One machine sequencing to minimize certain functions of job tardiness, Operations Research, 17, 701-715 (1969) · Zbl 0176.50005 |
| [27] | Emmons, H., Scheduling to a common due date on parallel common processors, Naval Research Logistics Quarterly, 34, 803-810 (1987) · Zbl 0648.90043 |
| [28] | Fawcett, S. E.; Pearson, J. N., Understanding and applying constraint management in today’s manufacturing environments, Production and Inventory Management Journal, 32, 46-55 (1991) |
| [29] | French, S., Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop (1982), Wiley: Wiley New York · Zbl 0479.90037 |
| [30] | Garey, M.; Tarjan, R.; Wilfong, G., One-processor scheduling with symmetric earliness and tardiness penalties, Mathematics of Operations Research, 13, 330-348 (1988) · Zbl 0671.90033 |
| [31] | 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 |
| [32] | 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 |
| [33] | Hax, A. C.; Candea, D., Production and Inventory Management (1984), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ |
| [34] | Kanet, J. J., Minimizing variation of flow time in single machine systems, Management Science, 27, 1453-1459 (1981) · Zbl 0473.90048 |
| [35] | 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 |
| [36] | Kise, H.; Ibaraki, T., On Balut’s algorithm and NP-completeness for a chance-constrained scheduling problem, Management Science, 29, 384-388 (1983) · Zbl 0513.90039 |
| [37] | McKay, K. N.; Safayeni, F. R.; Buzacott, J. A., Job-shop scheduling theory: What is relevant?, Interfaces, 18, 84-90 (1988) |
| [38] | Merten, A. G.; Muller, M. E., Variance minimization in single machine sequencing problems, Management Science, 18, 518-527 (1972) · Zbl 0254.90040 |
| [39] | Moore, J. M., An \(n\) job, one machine sequencing algorithm for minimizing the number of late jobs, Management Science, 15, 102-109 (1968) · Zbl 0164.20002 |
| [40] | Ow, P.; Morton, T., Filtered beam search in scheduling, International Journal of Production Research, 26, 35-62 (1988) |
| [41] | Ow, P.; Morton, T., The single machine early-tardy problem, Management Science, 35, 177-191 (1989) · Zbl 0666.90043 |
| [42] | Panwalkar, S.; Smith, M.; 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 |
| [43] | Pinedo, M. L., Stochastic scheduling with release dates and due dates, Operations Research, 31, 559-572 (1983) · Zbl 0523.90046 |
| [44] | Potts, C. N.; Van Wassenhove, L. N., A decomposition algorithm for the single machine total tardiness problem, Operations Research Letters, 1, 177-181 (1982) · Zbl 0508.90045 |
| [45] | Potts, C. N.; Van Wassenhove, L. N., Single machine tardiness sequencing heuristics, IIE Transactions, 23, 346-354 (1991) |
| [46] | Sarin, S. C.; Erel, E.; Steiner, G., Sequencing jobs on a single machine with a common due date and stochastic processing times, European Journal of Operational Research, 51, 188-198 (1991) · Zbl 0741.90037 |
| [47] | Schrage, L., Minimizing the time-in-system variance for a finite job set, Management Science, 21, 540-543 (1975) · Zbl 0302.90021 |
| [48] | Schrage, L.; Baker, K. R., Dynamic programming solution of sequencing problems with precedence constraints, Operations Research, 26, 444-449 (1978) · Zbl 0383.90054 |
| [49] | Sen, T.; Borah, B. N., On the single machine scheduling problem with tardiness penalties, Journal of the Operational Research Society, 42, 695-702 (1991) · Zbl 0743.90068 |
| [50] | Soroush, H., Risk taking in stochastic single machine scheduling (1991), Department of Management, Clemson University: Department of Management, Clemson University Clemson, SC, Working Paper |
| [51] | Sundararaghavan, P.; Ahmed, M., Minimizing the sum of absolute lateness in single machine and multimachine scheduling, Naval Research Logistics Quarterly, 31, 325-333 (1984) · Zbl 0544.90052 |
| [52] | Szwarc, W., Minimizing absolute lateness in single machine scheduling with different due dates (1988), University of Wisconsin: University of Wisconsin Milwaukee, WI, Working Paper |
| [53] | Taylor, S. G.; Bolander, S. F., Process flow scheduling principles, Production and Inventory Management Journal, 32, 67-71 (1991) |
| [54] | Umble, M. M.; Srikanth, M. L., Synchronous Manufacturing (1990), South-Western Publishing Co: South-Western Publishing Co Cincinnati, OH |
| [55] | Vani, V.; Raghavachari, M., Deterministic and random single machine sequencing with variance minimization, Operations Research, 35, 111-120 (1987) · Zbl 0616.90027 |
| [56] | White, D. J., Dynamic Programming (1969), Holden-Day: Holden-Day San Francisco, Ca · Zbl 0211.22801 |
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.
