×
Toksarı, M. Duran

A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs. (English) Zbl 1208.90080

Comput. Oper. Res. 38, No. 9, 1361-1365 (2011).
Summary: We present a single-machine problem with the unequal release times under learning effect and deteriorating jobs when the objective is minimizing the makespan. In this study, we introduced a scheduling model with unequal release times in which both job deterioration and learning exist simultaneously. By the effects of learning and deterioration, we mean that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. A branch-and-bound algorithm incorporating with several dominance properties and lower bounds is developed to derive the optimal solution. A heuristic algorithm is proposed to obtain a near-optimal solution. The computational experiments show that the branch-and-bound algorithm can solve instances up to 30 jobs, and the average error percentage of the proposed heuristic is less than 0.16%.

Cited in 10 Documents

MSC:

90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming

Keywords:

scheduling; single machine scheduling; learning effect; deterioration jobs; release times; makespan
PDF BibTeX XML Cite
\textit{M. D. Toksarı}, Comput. Oper. Res. 38, No. 9, 1361--1365 (2011; Zbl 1208.90080)
Full Text: DOI

References:

[1] Toksarı, M. D.; Guner, E., Minimizing the earliness/tardiness costs on parallel machine with learning effects and deteriorating jobs: a mixed nonlinear integer programming approach, International Journal of Advanced Manufacturing Technology, 38, 7-8, 801-808 (2008)
[2] Gupta, J. N.D.; Gupta, S. K., Single facility scheduling with nonlinear processing times, Computers and Industrial Engineering, 14, 387-393 (1988)
[3] Kunnathur, A. S.; Gupta, S. K., Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem, European Journal of Operational Research, 47, 56-64 (1990) · Zbl 0717.90034
[4] Mosheiov, G., V-shaped policies for scheduling deteriorating jobs, Operations Research, 39, 979-991 (1991) · Zbl 0748.90033
[5] Mosheiov, G., Scheduling jobs under simple linear deterioration, Computers and Operations Research, 21, 653-659 (1994) · Zbl 0810.90074
[6] Wright, T. P., Factors affecting the cost of airplanes, Journal of Aeronautical Sciences, 3, 122-128 (1936)
[7] OkoŁowski, D.; Gawiejnowicz, S., Exact and heuristic algorithms for parallel-machine scheduling with DeJong’s learning effect, Computers & Industrial Engineering, 59, 2, 272-279 (2010)
[8] Badiru, A. B., Computational survey of univariate and multivariate learning curve models, IEEE Transactions on Engineering Management, 39, 176-188 (1992)
[9] Globerson, S.; Seidmann, A., The effects of imposed learning curves on performance improvements, IIE Transactions, 20, 317-324 (1988)
[10] Raccoon, L. B., A learning curve primer for software engineers, Software Engineering Notes, 21, 77-86 (1995)
[11] Mosheiov, G., Scheduling problems with a learning effect, European Journal of Operational Research, 132, 687-693 (2001) · Zbl 1017.90051
[12] Wang, J. B., Single-machine scheduling problems with the effects of learning and deterioration, Omega, 35, 4, 397-402 (2007)
[14] Toksari, M. D.; Güner, E., Parallel machine scheduling problem to minimize the earliness/tardiness costs with learning effect and deteriorating jobs, Journal of Intelligent Manufacturing, 21, 6, 843-851 (2010)
[15] Wang, J. B.; Wang, D.; Zhang, G. D., Single-machine scheduling problems with both deteriorating jobs and learning effects, Applied Mathematical Modelling, 34, 10, 2831-2839 (2010) · Zbl 1201.90089
[17] Xingong, Z.; Guangle, Y., Single-machine group scheduling problems with deteriorated and learning effect, Applied Mathematics and Computation, 216, 4, 1259-1266 (2010) · Zbl 1187.90147
[18] Wang, J. B.; Guo, Q., A due-date assignment problem with learning effect and deteriorating jobs, Applied Mathematical Modelling, 34, 2, 309-310 (2010) · Zbl 1185.90099
[19] Huang, X.; Wang, J. B.; Wang, L. Y.; Gao, W. J.; Wang, X. R., Single machine scheduling with time-dependent deterioration and exponential learning effect, Computers and Industrial Engineering, 58, 1, 58-63 (2010)
[20] Toksari, M. D.; Güner, E., The common due-date early/tardy scheduling problem on a parallel machine under the effects of time-dependent learning and linear and nonlinear deterioration, Expert Systems with Applications, 37, 1, 92-112 (2010)
[21] Wang, J. B., Single-machine scheduling with learning effect and deteriorating jobs, Computers and Industrial Engineering, 57, 4, 1452-1456 (2009)
[22] Sun, L., Single-machine scheduling problems with deteriorating jobs and learning effects, Computers and Industrial Engineering, 57, 3, 843-846 (2009)
[23] Wang, J. B.; Liu, L. L., Two-machine flow shop problem with effects of deterioration and learning, Computers and Industrial Engineering, 57, 3, 1114-1121 (2009)
[24] Toksari, M. D.; Güner, E., Parallel machine earliness/tardiness scheduling problem under the effects of position based learning and linear/nonlinear deterioration, Computers and Operations Research, 36, 8, 2394-2417 (2009) · Zbl 1179.90158
[25] Toksari, M. D.; Oron, D.; Güner, E., Single machine scheduling problems under the effects of nonlinear deterioration and time-dependent learning, Mathematical and Computer Modelling, 50, 3-4, 401-406 (2009) · Zbl 1185.90097
[26] Cheng, T. C.E.; Wu, C. C.; Lee, W.-C., Some scheduling problems with deteriorating jobs and learning effects, Computers and Industrial Engineering, 54, 4, 972-982 (2008)
[27] Wang, X.; Cheng, T. C.E., Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan, European Journal of Operational Research, 178, 1, 57-70 (2007) · Zbl 1110.90045
[28] Wu, C. C.; Liu, C. L., Minimizing the makespan on a single machine with learning and unequal release times, Computers and Industrial Engineering, 59, 3, 419-424 (2010)
[29] Lee, W. C.; Wu, C. C.; Hsu, P. H., A single-machine learning effect scheduling problem with release times, OMEGA: The International Journal of Management Science, 38, 1-2, 3-11 (2010)
[30] Eren, T., Minimizing the total weighted completion time on a single machine scheduling with release dates and a learning effect, Applied Mathematics and Computation, 208, 2, 355-358 (2009) · Zbl 1155.90380
[31] Biskup, D., Single-machine scheduling with learning considerations, European Journal of Operational Research, 115, 173-178 (1999) · Zbl 0946.90025
[32] Lenstra, J. K.; Rinnooy; Kan, A. H.G.; Brucker, P., Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, 343-362 (1977) · Zbl 0301.90025
[33] Nawaz, M.; Enscore, E. E.; Ham, I., A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, OMEGA: The International Journal of Management Science, 11, 91-95 (1983)
[34] Heizer, J.; Render, B., Operations management (2001), Prentice-Hall
[35] Hsu, Y. S.; Lin, B. M.T., Minimization of maximum lateness under linear deterioration, Omega, 31, 459-469 (2003)
[36] Bachman, A.; Cheng, T. C.E.; Janiak, A.; Ng, C. T., Scheduling start time dependent jobs to minimize the weighted total completion time, Journal of Operational Research Society, 53, 6, 668-693 (2002) · Zbl 1059.90063
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.