Abstract
The problem of scheduling optimally a given set of jobs on a single machine is studied. The lower and upper bounds on the admissible duration of each job are known. The optimality criterion of the schedule is the minimum total completion time of a given set of jobs. Some properties of the optimality region for a job permutation are investigated. Polynomial algorithms for constructing the optimality region for a job permutation and also for calculating the volume of this region are developed. The existence conditions of an empty optimality region for a job permutation are determined. A criterion for the existence of a job permutation with the maximum possible volume of the optimality region is established.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Allahverdi, A., Aydilek, H., and Aydilek, A., Single Machine Scheduling Problem with Interval Processing Times to Minimize Mean Weighted Completion Times, Comput. Oper. Res., 2014, vol. 51, pp. 200–207.
Goren, S. and Sabuncuoglu, I., Robustness and Stability Measures for Scheduling: Single-machine Environment, IIE Transact., 2008, vol. 40, pp. 66–83.
Pereira, J., The Robust (Minmax Regret) Single Machine Scheduling with Interval Processing Times and Total Weighted Completion Time Objective, Comput. Oper. Res., 2016, vol. 66, pp. 141–152.
Lu, C.-C., Lin, S.-W., and Ying, K.-C., Robust Scheduling on a Single Machine Total Flow Time, Comput. Oper. Res., 2012, vol. 39, pp. 1682–1691.
Sotskov, Y.N. and Werner, F., Sequencing and Scheduling with Inaccurate Data, Hauppauge, New York: Nova Science, 2014.
Braun, O., Lai, T.C., Schmidt, G., and Sotskov, Y.N., Stability of Johnson’s Schedule with Respect to Limited Machine Availability, Int. J. Product. Res., 2002, vol. 40, no. 17, pp. 4381–4400.
Davis, W. and Jones, A., A Real-time Production Scheduler for a Stochastic Manufacturing Environment, Int. J. Product. Res., 1988, vol. 1, no. 2, pp. 101–112.
Grabot, B. and Geneste, L., Dispatching Rules in Scheduling: A Fuzzy Approach, Int. J. Product. Res., 1994, vol. 32, no. 4, pp. 903–915.
Kasperski, A. and Zielinski, P., Possibilistic Minmax Regret Sequencing Problems with Fuzzy Parameters, IEEE Transact. Fuzzy Syst., 2011, vol. 19, pp. 1072–1082.
Sotskov, Y.N. and Egorova, N.G., Single Machine Scheduling Problem with Interval Processing Times and Total Completion Time Objective, Algorithms, 2018, vol. 11, no. 66, pp. 21–40.
Sotskov, Y.N. and Lai, T.-C., Minimizing Total Weighted Flow Time under Uncertainty Using Dominance and a Stability Box, Comput. Oper. Res., 2012, vol. 39, no. 6, pp. 1271–1289.
Lai, T.-C., Sotskov, Y.N., Egorova, N.G., and Werner, F., The Optimality Box in Uncertain Data for Minimising the Sum of the Weighted Job Completion Times, Int. J. Product. Res., 2018, vol. 56, no. 19, pp. 6336–6362.
Sotskov, Y.N. and Egorova, N.G., Stability Polyhedra of Optimal Permutation of Jobs Servicing, Autom. Remote Control, 2014, vol. 75, no. 7, pp. 1267–1282.
Sotskov, Y.N., Lai, T.-C., and Werner, F., Measures of Problem Uncertainty for Scheduling with Interval Processing Times, OR Spectrum, 2013, vol. 35, pp. 659–689.
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. Modell., 2009, vol. 50, pp. 556–573.
Lai, T.-C., Sotskov, Y.N., Sotskova, N., and Werner, F., Optimal Makespan Scheduling with Given Bounds of Processing Times, Math. Comput. Modell., 1997, vol. 26, no. 3, pp. 67–86.
Sotskov, Y.N., Egorova, N.G., and Werner, F., Minimizing Total Weighted Completion Time with Uncertain Data: a Stability Approach, Automat. Remote Control, 2010, vol. 71, no. 10, pp. 2038–2057.
Pinedo, M., Scheduling: Theory, Algorithms and Systems, Englewood Cliffs: Prentice Hall, 2002.
Graham, R.E., Lawler, E.L., Lenstra, J.K., and Rinnooy Kan, A.H.G., Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey, Ann. Discret. Math., 1979, vol. 5, pp. 287–326.
Smith, W., Various Optimizers for Single-stage Production, Naval Res. Logist. Quarterly, 1956, vol. 3, no. 1, pp. 59–66.
Kouvelis, P. and Yu, G., obust Discrete Optimization and Its Application, Boston: Kluwer, 1997.
Burdett, R.L. and Kozan, E., Techniques to Effectively Buffer Schedules in the Face of Uncertainties, Comput. Ind. Eng., 2015, vol. 87, pp. 16–29.
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.
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.
Yang, J. and Yu, G., On the Robust Single Machine Scheduling Problem, J. Combinat. Optim., 2002, vol. 6, pp. 17–33.
Harikrishnan, K.K. and Ishii, H., Single Machine Batch Scheduling Problem with Resource Dependent Setup and Processing Time in the Presence of Fuzzy Due Date, Fuzzy Optim. Decision Making, 2005, vol. 4, pp. 141–147.
Sotskov, Y.N. and Egorova, N.G., Single-machine Scheduling with Uncertain Durations for Optimizing Service Logistics with One Truck, EURO Mini-conf. Logist. Anal., Minsk, Belarus, June 18-19, 2018, p. 29.
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper was recommended for publication by A. A. Lazarev, a member of the Editorial Board
Russian Text © The Author(s), 2020, published in Avtomatika i Telemekhanika, 2020, No. 5, pp. 60–90.
Rights and permissions
About this article
Cite this article
Sotskov, Y.N. Optimality Region for Job Permutation in Single-Machine Scheduling with Uncertain Processing Times. Autom Remote Control 81, 819–842 (2020). https://doi.org/10.1134/S0005117920050045
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0005117920050045