Scheduling in stochastic bicriteria single machine systems with job-dependent learning effects
Keywords:
Bicriteria, learning effect, scheduling, single machine, stochasticAbstract
A stochastic bicriteria single machine scheduling problem with job-dependent learning effects in which the normal processing times of jobs (i.e., processing times without any learning effects) are random variables was studied. The job-dependent learning effects show that the random actual processing times are unique functions of the positions of jobs in a sequence. The goal was to derive the optimal sequence that minimizes the expected value of a general quadratic function of each pair of criteria consisting of the makespan, total completion time, total lateness, total waiting cost, total waiting time, total absolute differences in completion times, and the sum of earliness, tardiness and common due date penalty. The resultant problems were formulated as quadratic assignment problems that could be solved exactly or heuristically, and proved that their special cases with linear cost functions are solvable in polynomial time. Computational results on problems with quadratic assignment formulations indicated that near-optimal solutions can be obtained with attractive CPU times.
References
Adams, W. P. Johnson, T. A. 1994. Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS Series (AMS) 16: 43-75.
Adams, W. P., Guignard, M., Hahn, P. M. Hightower, W. L. 2007. A level-2 reformulation--linearization technique bound for the quadratic assignment problem. European Journal of Operational Research 180: 983-996.
Alidaee, B. 1993. Numerical methods for single machine scheduling with non-linear cost functions to minimize total cost. Journal of Operational Research Society 44: 125-132.
Angel, E., Bampis, E. Gourves, L. 2005. Approximation results for a bicriteria job scheduling problem on a single machine without preemption. Information Processing Letters 94: 19-27.
Badiru, A. B. 1992. Computational survey of univariate and multivariate learning curve models. IEEE Transactions on Engineering Management 39: 176-188.
Baker, K. R. Scudder, G. D. 1990. Sequencing with earliness and tardiness penalties: A review. Operations Research 38: 22-36.
Baker, K. R. Trietsch, D. 2009. Safe scheduling: Setting due dates in single-machine problems. European Journal of Operational Research 196: 69-77.
Biskup, D. 1999. Single-machine scheduling with learning considerations. European Journal of Operational Research 115: 173-178.
Biskup, D. 2008. A state-of-the-art review on scheduling with learning effects. European Journal of Operational Research 188: 315-329.
Chen, W. Y. Sheen, G. J. 2007. Single-machine scheduling with multiple performance measures: Minimizing job dependent earliness and tardiness subject to the number of tardy jobs. International Journal of Production Economics 109: 214-222.
Cheng, T. C. E. Wang, G. 2000. Single machine scheduling with learning effect considerations. Annals of Operations Research 98: 273-290.
Cheng, T. C. E., Lee, W. C Wu, C. C. 2010. Scheduling problems with deteriorating jobs and learning effects including proportional setup times. Computers and Industrial Engineering 58: 326-331.
Cheng, T. C. E., Lee, W. C Wu, C. C. 2011. Single-machine scheduling with deteriorating jobs and past-sequence-dependent setup times. Applied Mathematical Modelling 35: 1861-1867.
Eren, T. Guner, E. 2007. Minimizing total tardiness in a scheduling problem with a learning effect. Applied Mathematical Modelling 31: 1351-1361.
Erenay, F. S, Sabuncuoglu, I., Toptal, A. Tiwari, M.K. 2010. New solutions methods for single machine bicriteria scheduling problem: Minimization of average flowtime and number of tardy jobs. European Journal of Operational Research 201: 89-98.
Forst, F. G. 1995. Bicriterion stochastic scheduling on one or more machines. European Journal of Operational Research 80: 404-409.
Gawiejnowicz, S., Kurc, W. Pankowska, L. 2006. Pareto and scalar bicriterion optimization in scheduling deteriorating jobs. Computers Operation Research 33: 746-767.
Graham, R. L., Lawler, E. L., Lenstra, J. K. Rinnooy Kan, A. H. G. 1979. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics 5: 287-226.
Hoogeveen, H. 2005. Multicriteria scheduling. European Journal of Operational Research 167: 592-623.
Huang, X., Wang, J. B., Wang, L. Y., Gao, W. J. Wang, X. R. 2010. Single machine scheduling with time-dependent deterioration and exponential learning effect. Computers and Industrial Engineering 58: 58-63.
James, T., Rego, C. Glover, F. 2009. A cooperative parallel tabu search algorithm for the quadratic assignment problem. European Journal of Operational Research 195: 810-826.
Kanet, J. J. 1981. Minimizing variation of flow time in single machine systems. Management Science 27: 1453-1459.
Koksalan, M. Keha, A. B. 2003. Using genetic algorithms for single-machine bicriteria scheduling problems. European Journal of Operational Research 145: 543-556.
Keeney, R. L. Raiffa, H. 1976. Decisions with Multiple Objectives: Preferences and Value Tradeoffs. John Wiley: New York.
Lee, W. C., Wu, C. C. Sung, H. J. 2004. A bi-criterion single-machine scheduling problem with learning considerations. Acta Informat 40: 303-315.
Lee, W. C., Wu, C. C. Liu, M. F. 2009. A single-machine bi-criterion learning scheduling problem with release times. Expert Systems with Applications 36: 10295-10303.
Liu, Z. 2010. Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints. Computers Operations Research 37: 1537-1543.
Lu, S. Sun, C. 2011. Quadratic approximation based differential evolution with valuable trade off approach for bi-objective short-term hydrothermal scheduling. Expert Systems with Applications 38: 13950-13960.
Mani, V., Chang, P. C. Chen, S. H. 2009. Bi-criteria single machine scheduling problem with a learning effect: Aneja_Nair method to obtain the set of optimal sequences. Computers and Mathematics with Applications 58: 39-47.
Mazdeh, M., Shashaani, S., Ashouri, A. Hindi, K. S. 2011. Single-machine batch scheduling minimizing weighted flow times and delivery costs. Applied Mathematical Modelling 35: 563-570.
Molaee, E., Moslehi, G. Reisi, M. 2010. Minimizing maximum earliness and number of tardy jobs in the single machine scheduling problem. Computers and Mathematics with Applications 60: 2909-2919.
Mosheiov, G. 2001. Scheduling problems with a learning effect. European Journal of Operational Research 132: 687-693.
Mosheiov, G. Sidney, J. B. 2003. Scheduling with general job-dependent learning curves. European Journal of Operational Research 147: 665--670.
Mosheiov, G. Sidney, J. B. 2005. Note on scheduling with general learning curves to minimize number of tardy jobs. Journal of the Operational Research Society 56: 110-112.
Panwalkar, S. S., Smith, M. L. Seidmann, A. 1982. Common due date assignment to minimize total penalty for the one machine scheduling problem. Operations Research 30: 391-399.
Papadimitriou, C. H. Steiglitz, K. 1982. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall: Englewood Cliffs, NJ.
Shabtay, D., Steiner, G. Yedidsion, L. 2010. Bicriteria problems to minimize maximum tardiness and due date assignment cost in various scheduling environments. Discrete Applied Mathematics 158: 1090-1103.
Shabtay, D. Steiner, G. 2011. A bicriteria approach to minimize the total weighted number of tardy jobs with convex controllable processing times and assignable due dates. Journal of Scheduling 14: 455-469.
Soroush, H. M. 2007. Minimizing the weighted number of early and tardy jobs in a stochastic single machine scheduling problem. European Journal of Operational Research 181: 266-287.
Soroush, H. M. 2010a. Solving a stochastic single machine problem with initial idle time and quadratic objective. Computers Operations Research 37: 1328-1347.
Soroush, H. M. 2010b. Single machine scheduling with inserted idle time to minimize a weighted quadratic function of job lateness. European Journal of Industrial Engineering 4: 131-166.
Soroush, H. M. 2011. Scheduling in stochastic bicriteria single machine systems with set-up times, International Journal of Planning and Scheduling 1: 109-145.
Soroush, H. M. 2012. Solving the single machine scheduling problem with general job-dependent past-sequence-dependent setup times and learning effects. European Journal of Industrial Engineering 6: 596-628.
Soroush, H. M. 2013a. Scheduling in bicriteria single machine systems with past-sequence-dependent setup times and learning effects. Journal of Operational Research Society. DOI:10.1057/jors.2013.43.
Soroush, H. M. 2013b. Stochastic bicriteria single machine scheduling with quadratic cost functions. International Journal of Operational Research 17: 59-103.
Soroush, H. M. 2013c. Stochastic bicriteria single machine scheduling with sequence-dependent job attributes and job-dependent learning effects. European Journal of Industrial Engineering. (in press).
Soroush, H. M. Fredendall, L. D. 1994. The stochastic single machine scheduling problem with earliness and tardiness costs. European Journal of Operational Research 77: 287-302.
Soroush, H. M. Alqallaf, F. A. 2009. Minimizing a weighted quadratic function of job lateness in the stochastic single machine scheduling problem. International Journal of Operational Research 6: 538-572.
Sotskov, Y. N. Lai, T. C. 2012. Minimizing total weighted flow time under uncertainty using dominance and a stability box. Computers and Operations Research 39: 1271-1289.
Steiner, G. Stephenson, P. 2007. Pareto optima for total weighted completion time and maximum lateness on a single machine. Discrete Applied Mathematics 155: 2341-2354.
T'Kindt, V. Billaut, J. C. 2001. Multicriteria scheduling problems: a survey. RAIRO Operations Research 35: 143-163.
T'kindt, V. Billaut, J. C. 2002. Multicriteria Scheduling: Theory, Models and Algorithms. Springer: Berlin.
Umble, M. M. Srikanth, M. L. 1995. Synchronous manufacturing: Principles for world-class excellence. Spectrum Publication Company: Wallingford, CT.
Valente, J. M. S. Gon٥alves, J. F. 2009. A genetic algorithm approach for the single machine scheduling problem with linear earliness and quadratic tardiness penalties. Computers and Operations Research 36: 2707-2715.
Wang, J. B. Li, J. X. 2011. Single machine past-sequence-dependent setup times scheduling with general position-dependent and time-dependent learning effects. Applied Mathematical Modelling 35: 1388-1395.
Wang, J. B. Wang, M. Z. 2012. Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time. Computers Operations Research 39: 492-497.
Wang, J. B, Wang, D., Wang, L.Y., Lin, L., Yin, N. Wang, W. W. 2009. Single machine scheduling with exponential time-dependent learning effect and past-sequence-dependent setup times. Computers and Mathematics with Applications 57: 9-16.
Wei, C. M. Wang, J. B. 2010. Single machine quadratic penalty function scheduling with deteriorating jobs and group technology. Applied Mathematical Modelling 34: 3642-3647.
Wright, T. P. 1936. Factors affecting the cost of airplanes. Journal of Aeronautical Sciences 3: 122-128.
Wu, C. C., Lee W. C. Chen, T. 2007. Heuristic algorithms for solving the maximum lateness scheduling problem with learning considerations. Computers and Industrial Engineering 52: 124-132.
Xia, Y. 2010. An efficient continuation method for quadratic assignment problems. Computers Operations Research 37: 1027-1032.
Yedidsion, L., Shabtay, D., Korach, E., Kaspi, M. 2009. A bicriteria approach to minimize number of tardy jobs and resource consumption in scheduling a single machine. International Journal of Production Economics 119: 298-307.
Yelle, L. E. 1979. The learning curve: Historical review and comprehensive survey. Decision Science 10: 302-328.
Zhang. X. Yan, G. 2010. Machine scheduling problems with a general learning effect. Mathematical and Computer Modelling 51: 84-90.
Zhang, H., Beltran-Royo, C. Constantino, M. 2010. Effective formulation reductions for the quadratic assignment problem. Computers Operations Research 37: 2007-2016.
Zhao, C.L., Zhang, Q.L. Tang, H.Y. 2004. Machine scheduling problems with learning effects. Dynamics of Continuous, Discrete and Impulsive Systems, Series A: Mathematical Analysis 11: 741-750.
