No Access

MAKESPAN MINIMIZATION ON THREE-MACHINE FLOW SHOP WITH DETERIORATING JOBS

JI-BO WANG

School of Science, Shenyang Aerospace University, Shenyang 110136, China

State Key Laboratory for Manufacturing Systems Engineering, (Xi'an Jiaotong University), Xi'an 710053, China

Corresponding author.

Search for more papers by this author

and

MING-ZHENG WANG

School of Management Science and Engineering, Dalian University of Technology, Dalian 116024, China

Search for more papers by this author

https://doi.org/10.1142/S021759591350022XCited by:9 (Source: Crossref)

Abstract

In this study, we consider a permutation flow shop scheduling problem on a three-machine with deteriorating jobs (a deteriorating job means that the job's processing time is an increasing function of its starting time) so as to minimize the makespan. We model job deterioration as a function that is proportional to a linear function of time. For some special cases, we prove that the problem can be solved in polynomial time. We develop branch-and-bound and heuristic procedures for the general case. Computational experiments for the branch-and-bound algorithm and heuristic algorithm are presented.

Keywords:

References

S. Browne and U. Yechiali, Operations Research 38, 495 (1990), DOI: 10.1287/opre.38.3.495. Web of Science, Google Scholar
T. C. E. Chenget al., Computers and Operations Research 38, 1760 (2011), DOI: 10.1016/j.cor.2010.11.014. Web of Science, Google Scholar
T. C. E. Cheng, W.-C. Lee and C.-C. Wu, Applied Mathematical Modelling 35, 1861 (2011), DOI: 10.1016/j.apm.2010.10.015. Web of Science, Google Scholar
T. C. E. Cheng, C. C. Wu and W. C. Lee, Computers and Industrial Engineering 54(4), 972 (2008), DOI: 10.1016/j.cie.2007.11.006. Web of Science, Google Scholar
T. C. E. Chenget al., Applied Mathematics and Computation 217, 8804 (2011), DOI: 10.1016/j.amc.2011.04.005. Web of Science, Google Scholar
Gawiejnowicz, S (2008). Time-Dependent Scheduling. Berlin: Springer . Google Scholar
E. Ignall and L. E. Schrage, Operations Research 13, 400 (1965), DOI: 10.1287/opre.13.3.400. Web of Science, Google Scholar
M. Ji and T. C. E. Cheng, European Journal of Operational Research 188(2), 342 (2008), DOI: 10.1016/j.ejor.2007.04.050. Web of Science, Google Scholar
M. Ji and T. C. E. Cheng, Theoretical Computer Science 410, 3761 (2008), DOI: 10.1016/j.tcs.2009.04.018. Web of Science, Google Scholar
M. Ji and T. C. E. Cheng, Computers and Industrial Engineering 59, 794 (2010), DOI: 10.1016/j.cie.2010.08.005. Web of Science, Google Scholar
M. Ji and T. C. E. Cheng, European Journal of Operational Research 202(1), 90 (2010), DOI: 10.1016/j.ejor.2009.05.021. Web of Science, Google Scholar
Kononov, A (1999). On the complexity of the problems of scheduling with time-dependent job processing times. Ph.D. dissertation, Sobolev Institute of Mathematics, Novosibirsk, p. 106 (in Russian) . Google Scholar
A. Kononov and S. Gawiejnowicz, Journal of the Operational Research Society 52, 708 (2001), DOI: 10.1057/palgrave.jors.2601117. Web of Science, Google Scholar
W.-C. Leeet al., International Journal of Production Economics 124, 188 (2010), DOI: 10.1016/j.ijpe.2009.11.001. Web of Science, Google Scholar
W.-C. Leeet al., Computers and Operations Research 36, 2111 (2009), DOI: 10.1016/j.cor.2008.07.008. Web of Science, Google Scholar
W.-C. Leeet al., Computers and Industrial Engineering 54, 737 (2008), DOI: 10.1016/j.cie.2007.10.010. Web of Science, Google Scholar
S. S. Liet al., European Journal of Operational Research 210, 482 (2011), DOI: 10.1016/j.ejor.2010.11.021. Web of Science, Google Scholar
G. Mosheiov, Discrete Applied Mathematics 117, 195 (2002), DOI: 10.1016/S0166-218X(00)00385-1. Web of Science, Google Scholar
G. Mosheiov, A. Sarig and J. Sidney, Computers and Operations Research 37, 1965 (2010), DOI: 10.1016/j.cor.2010.01.006. Web of Science, Google Scholar
C. T. Nget al., Computers and Operations Research 37, 83 (2010), DOI: 10.1016/j.cor.2009.03.019. Web of Science, Google Scholar
C. T. Nget al., Computers and Industrial Engineering 61, 647 (2011), DOI: 10.1016/j.cie.2011.04.020. Web of Science, Google Scholar
Y.-R. Shiauet al., International Journal of Advanced Manufacture Technology 34, 774 (2007), DOI: 10.1007/s00170-006-0646-8. Web of Science, Google Scholar
L. Tang and P. Liu, Applied Mathematical Modelling 33, 1187 (2009), DOI: 10.1016/j.apm.2008.01.013. Web of Science, Google Scholar
L. Tang and P. Liu, Computers and Industrial Engineering 56, 1289 (2009), DOI: 10.1016/j.cie.2008.07.022. Web of Science, Google Scholar
J.-B. Wang, Computers and Operational Research 34, 2043 (2007), DOI: 10.1016/j.cor.2005.08.008. Web of Science, Google Scholar
J.-B. Wang and T. C. E. Cheng, Asia-Pacific Journal of Operational Research 24, 245 (2007), DOI: 10.1142/S021759590700122X. Link, Web of Science, Google Scholar
J.-B. Wang, T. C. E. Cheng and L.-L. Liu, Applied Mathematics and Computation 180, 185 (2006), DOI: 10.1016/j.amc.2005.11.162. Web of Science, Google Scholar
J.-B. Wang and M.-Z. Wang, Computers and Operations Research 40, 547 (2013), DOI: 10.1016/j.cor.2012.08.006. Web of Science, Google Scholar
J.-B. Wang, M.-Z. Wang and P. Ji, Asia-Pacific Journal of Operational Research 29(5), 1250030 (2012), DOI: 10.1142/S0217595912500303. Link, Web of Science, Google Scholar
J.-B. Wang and Z.-Q. Xia, Journal of the Operational Research Society 57, 220 (2006). Web of Science, Google Scholar
L. Wanget al., International Journal of Production Economics 125, 185 (2010), DOI: 10.1016/j.ijpe.2010.01.021. Web of Science, Google Scholar
C.-C. Wu and W.-C. Lee, International Journal of Production Economics 103, 572 (2006), DOI: 10.1016/j.ijpe.2005.11.005. Web of Science, Google Scholar
C.-C. Wu, W.-C. Lee and Y.-R. Shiau, Asia-Pacific Journal of Operational Research 28, 349 (2011), DOI: 10.1142/S0217595911003272. Link, Web of Science, Google Scholar
S.-J. Yang, D.-L. Yang and T. C. E. Cheng, Computers and Operations Research 37, 1510 (2010), DOI: 10.1016/j.cor.2009.11.007. Web of Science, Google Scholar
C. Zhao, Q. Zhang and H. Tang, Acta Automatica Sinica 29, 531 (2003). Web of Science, Google Scholar
C. Zhao and H. Tang, Asia-Pacific Journal of Operational Research 28, 419 (2011), DOI: 10.1142/S0217595911003302. Link, Web of Science, Google Scholar