Minimizing total weighted completion time with uncertain data: a stability approach. (English. Russian original) Zbl 1203.93130
Autom. Remote Control 71, No. 10, 2038-2057 (2010); translation from Avtom. Telemekh. 2010, No. 10, 26-49 (2010).
Summary: A single-machine scheduling problem is investigated provided that the input data are uncertain: The processing time of a job can take any real value from the given segment. The criterion is to minimize the total weighted completion time for the \(n\) jobs. As a solution concept to such a scheduling problem with an uncertain input data, it is reasonable to consider a minimal dominant set of job permutations containing an optimal permutation for each possible realization of the job processing times. To find an optimal or approximate permutation to be realized, we look for a permutation with the largest stability box being a subset of the stability region. We develop a branch-and-bound algorithm to construct a permutation with the largest volume of a stability box. If several permutations have the same volume of a stability box, we select one of them due to one of two simple heuristics. The efficiency of the constructed permutations (how close they are to a factually optimal permutation) and the efficiency of the developed software (average CPU-time used for an instance) are demonstrated on a wide set of randomly generated instances with \(5 \leq n \leq 100\).
MSC:
| 93C83 | Control/observation systems involving computers (process control, etc.) |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 93D09 | Robust stability |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 93C41 | Control/observation systems with incomplete information |
Keywords:
uncertain data; single-machine scheduling problem; optimal permutation for each possible realization; branch-and-bound algorithm; stability boxReferences:
| [1] | Pinedo, M., Scheduling: Theory, Algorithms, and Systems, New Jersey: Prentice Hall, 2002. · Zbl 1145.90394 |
| [2] | Aytug, H., Lawley, M.A., McKay, K., Mohan, S., and Uzsoy, R., Executing Production Schedules in the Face of Uncertainties: A Review and Some Future Directions, Eur. J. Oper. Res., 2005, vol. 161, pp. 86–110. · Zbl 1115.90025 · doi:10.1016/j.ejor.2003.08.027 |
| [3] | Sabuncuoglu, I. and Goren, S., Hedging Production Schedules Against Uncertainty in Manufacturing Environment with a Review of Robustness and Stability Research, Int. J. Comput. Integrated Manufacturing, 2009, vol. 22, no. 2, pp. 138–157. · doi:10.1080/09511920802209033 |
| [4] | Daniels, R.L. and Kouvelis, P., Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production, Manage. Sci., 1995, vol. 41, no. 2, pp. 363–376. · Zbl 0832.90050 · doi:10.1287/mnsc.41.2.363 |
| [5] | Kouvelis, P. and Yu, G., Robust Discrete Optimization and Its Applications, Boston: Kluwer, 1997. · Zbl 0873.90071 |
| [6] | Yang, J. and Yu, G., On the Robust Single Machine Scheduling Problem, J. Combinat. Optim., 2002, vol. 6, pp. 17–33. · Zbl 1058.90029 · doi:10.1023/A:1013333232691 |
| [7] | Lai, T.-C., Sotskov, Y.N., Sotskova, N., and Werner, F., Optimal Makespan Scheduling with Given Bounds of Processing Times, Math. Comput. Model., 1997, vol. 26, pp. 67–86. · Zbl 0895.90118 |
| [8] | Lai, T.-C. and Sotskov, Y.N., Sequencing with Uncertain Numerical Data for Makespan Minimization, J. Oper. Res. Soc., 1999, vol. 50, pp. 230–243. · Zbl 1054.90549 · doi:10.1057/palgrave.jors.2600690 |
| [9] | Sotskov, Y.N. and Sotskova, N.Y., Teoriya raspisanii: sistemy s neopredelennymi chislovymi parametrami (Scheduling Theory: Systems with Uncertain Numerical Parameters), Minsk: Natl. Acad. Sci. Belarus, United Inst. of Informatics Problems, 2004. |
| [10] | Matsveichuk, N.M., Sotskov, Y.N., Egorova, N.G., and Lai, T.-C., Schedule Execution for Two-Machine Flow-Shop with Interval Processing Times, Math. Comput. Modelling, 2009, vol. 49, nos. 5–6, pp. 991–1011. · Zbl 1165.90464 · doi:10.1016/j.mcm.2008.02.004 |
| [11] | Sotskov, Y.N., Egorova, N.G., and Lai, T.-C., Minimizing Total Weighted Flow Time of a Set of Jobs with Interval Processing Times, Math. Comput. Modelling, 2009, vol. 50, pp. 556–573. · Zbl 1185.90094 · doi:10.1016/j.mcm.2009.03.006 |
| [12] | Lai, T-C, Sotskov, Y.N., Sotskova, N.Y., and Werner, F., Mean Flow Time Minimization with Given Bounds of Processing Times, Eur. J. Oper. Res., 2004, vol. 159, no. 3, pp. 558–573. · Zbl 1065.90038 · doi:10.1016/S0377-2217(03)00424-7 |
| [13] | Sotskov, Y.N., Wagelmans, A.P.M., and Werner, F., On the Calculation of the Stability Radius of an Optimal or an Approximate Schedule, Ann. Oper. Res., 1998, vol. 83, pp. 213–252. · Zbl 0911.90222 · doi:10.1023/A:1018960030420 |
| [14] | Sotskov, Y.N., Sotskova, N.Y., and Werner, F., Stability of an Optimal Schedule in a Job Shop, Omega, 1997, vol. 25, no. 4, pp. 397–414. · doi:10.1016/S0305-0483(97)00012-1 |
| [15] | Graham, R.L., Lawler, E.L., Lenstra, J.K., and Rinnooy Kan, A.H.G., Optimization and Approximation in Deterministic Sequencing and Scheduling. A Survey, Ann. Discr. Math., 1976, vol. 5, pp. 287–326. · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [16] | Smith, W.E., Various Optimizers for Single-Stage Production, Nav. Res. Logist. Quarterly, 1956, vol. 3, no. 1, pp. 59–66. · doi:10.1002/nav.3800030106 |
| [17] | Kasperski, A. and Zielinski, P., A 2-approximation Algorithm for Interval Data Minmax Regret Sequencing Problems with Total Flow Time Criterion, Oper. Res. Lett., 2008, vol. 36, pp. 343–344. · Zbl 1151.90417 · doi:10.1016/j.orl.2007.11.004 |
| [18] | Montemanni, R., A Mixed Integer Programming Formulation for the Total Flow Time Single Machine Robust Scheduling Problem with Interval Data, J. Math. Model. Algorith., 2007, vol. 6, pp. 287–296. · Zbl 1152.90455 · doi:10.1007/s10852-006-9044-3 |
| [19] | Sotskov, Y.N., Dolgui, A., and Portmann, M.-C., Stability Analysis of Optimal Balance for Assembly Line with Fixed Cycle Time, Eur. J. Oper. Res., 2006, vol. 168, no. 3, pp. 783–797. · Zbl 1102.90321 · doi:10.1016/j.ejor.2004.07.028 |
| [20] | Sotskov, Y.N., Stability of an Optimal Schedule, Eur. J. Oper. Res., 1991, vol. 55, pp. 91–102. · Zbl 0755.90048 · doi:10.1016/0377-2217(91)90194-Z |
| [21] | Sotskov, Y.N., Tanaev, V.S., and Werner, F., Stability Radius of an Optimal Schedule: A Survey and Recent Developments, in Industr. Appl. Combinat. Optim., Yu, G., Ed., Boston: Kluwer, 1998, pp. 72–108. · Zbl 0936.90030 |
| [22] | Sotskova, N.Y. and Tanaev, V.S., About the Realization of an Optimal Schedule with Operation Processing Times under Conditions of Uncertainty, Dokl. Natl. Akad. Nauk Belarusi, 1998, vol. 42, no. 5, pp. 8–12. · Zbl 1039.90512 |
| [23] | Allahverdi, A. and Sotskov, Y.N., Two-machine Flowshop Minimum-length Scheduling Problem with Random and Bounded Processing Times, Int. Transactions Oper. Res., 2003, vol. 10, pp. 65–76. · Zbl 1027.90026 · doi:10.1111/1475-3995.00393 |
| [24] | Allahverdi, A., Aldowaisan, T., and Sotskov, Y.N., Two-machine Flowshop Scheduling Problem to Minimize Makespan or Total Completion Time with Random and Bounded Setup Times, Int. J. Math. Math. Sci., 2003, vol. 39, pp. 2475–2486. · Zbl 1041.90020 · doi:10.1155/S016117120321019X |
| [25] | Ng, C.T., Matsveichuk, N.M., Sotskov, Y.N., and Cheng, T.C.E., Two-machine Flow-shop Minimumlength Scheduling with Interval Processing Times, Asia-Pacific J. Oper. Res., 2009, vol. 26, no. 6, pp. 1–20. · Zbl 1180.90134 · doi:10.1142/S0217595909002432 |
| [26] | Sotskov, Y.N., Allahverdi, A., and Lai, T.-C., Flowshop Scheduling Problem to Minimize Total Completion Time with Random and Bounded Processing Times, J. Oper. Res. Soc., 2004, vol. 55, pp. 277–286. · Zbl 1095.90049 · doi:10.1057/palgrave.jors.2601682 |
| [27] | Computer and Job-Shop Scheduling Theory, Coffman, E.G., Ed., New York: Wiley, 1976. |
| [28] | Sotskov, Y.N. and Lai, T.-C., Minimizing Total Weighted Completion Time under Uncertainty Using Stability Box and Dominance, Comput. Oper. Res. (submitted). · Zbl 1251.90190 |
| [29] | Emelichev, V.A., Girlich, E.N., Nikulin, Y.V., and Podkopaev, D.P., Stability and Regularization Radius of Vector Problems of Integer Linear Programming. Optimization, 2002, vol. 51, no. 4, pp. 645–676. · Zbl 1109.90325 · doi:10.1080/0233193021000030760 |
| [30] | Emelichev, V.A., Krichko, V.N., and Nikulin, Y.V., The Stability Radius of an Efficient Solution in Mimimax Boolean Programming Problem. Control Cybernet., 2004, vol. 33, no. 1, pp. 127–132. · Zbl 1115.90035 |
| [31] | Emelichev, V.A., Kuz’min, K.G., and Leonovich, A.M., Stability in the Combinatorial Vector Optimization Problems. Autom. Remote Control, 2004, vol. 65, no. 2, pp. 227–240. · Zbl 1066.90113 · doi:10.1023/B:AURC.0000014719.45368.36 |
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.
