تعداد نشریات | 27 |
تعداد شمارهها | 566 |
تعداد مقالات | 5,825 |
تعداد مشاهده مقاله | 8,162,063 |
تعداد دریافت فایل اصل مقاله | 5,460,765 |
SINGLE MACHINE DUE DATE ASSIGNMENT SCHEDULING PROBLEM WITH PRECEDENCE CONSTRAINTS AND CONTROLLABLE PROCESSING TIMES IN FUZZY ENVIRONMENT | ||
Iranian Journal of Fuzzy Systems | ||
مقاله 9، دوره 15، شماره 6، بهمن و اسفند 2018، صفحه 121-143 اصل مقاله (705.99 K) | ||
نوع مقاله: Research Paper | ||
شناسه دیجیتال (DOI): 10.22111/ijfs.2018.4371 | ||
نویسندگان | ||
Jinquan Li ![]() | ||
1School of Applied Mathematics, Zhuhai Municipal Key Laboratory of Intelligent Control, Beijing Normal University Zhuhai, Zhuhai 519087, P.R. China | ||
2School of Science, East China University of Technology, Nanchang 330013, P.R. China | ||
3School of Electronic and Information Engineering, Dalian University of Technology, Dalian 116024, P.R. China | ||
چکیده | ||
In this paper, a due date assignment scheduling problem with precedence constraints and controllable processing times in uncertain environment is investigated, in which the basic processing time of each job is assumed to be the symmetric trapezoidal fuzzy number, and the linear resource consumption function is used. The objective is to minimize the crisp possibilistic mean (or expected) value of a cost function that includes the costs of earliness, tardiness, makespan and resource consumption jointly by scheduling the jobs under precedence constraints and determining the due date and the resource allocation amount satisfying resource constraints for each job. First, the problem is shown to be NP-hard. Furthermore, an optimal algorithm with polynomial time for the special case of this problem is put forward. Moreover, an efficient 2-approximation algorithm is presented based on solving the relaxation of the problem. Finally, the numerical experiment is given, whose results show that our method is promising. | ||
کلیدواژهها | ||
Fuzzy scheduling؛ Fuzzy number؛ Possibilistic mean value and variance؛ Due date assignment scheduling؛ Precedence constraints؛ Controllable processing times | ||
مراجع | ||
[1] L.D. Adolphson, Sinle machine job sequencing with precedence constraints, SIAM Journal on Computing, 6(1) (1977), 40–54. [2] R. Alvarez-Valdes, J.M. Tamarit and F. Villa, Minimizing weighted earliness-tardiness on parallel machines using hybrid metaheuristics, Computers & Operations Research, 54 (2015), 1–11. [3] P. Assarzadegan and M. Rasti-Barzoki,Minimizing sum of the due date assignment costs, maximumtardiness and distribution costs in a supply chain scheduling problem, Applied Soft Computing, 47 (2016), 343–356. [4] K.R. Baker, Minimizing earliness and tardiness costs in stochastic scheduling, European Journal of Operational Research, 236(2) (2014), 445–452. [5] C. Carlsson and R. Full´er, On possibilistic mean value and variance of fuzzy numbers, Fuzzy Sets and Systems, 122(2) (2001), 315–326. [6] T.C.E. Cheng, Optimal assignment of slack due-dates and sequencing of jobs with random processing times on a single machine, European Journal of Operational Research, 51(3) (1991), 348–353. [7] T.C.E. Cheng, C. O˘guz and X. Qi, Due-date assignment and single machine scheduling with compressible processing times, International Journal of Production Economics, 43(2-3) (1996), 107–113. [8] D. Du, Ker-I Ko and X. Hu, Design and Analysis of Approximation Algorithms, Springer Press, New York, 2012. [9] R. Full´er and P. Majlender, On weighted possibilistic mean and variance of fuzzy numbers, Fuzzy Sets and Systems, 136(3) (2003), 363–374. [10] V. Gordon, J. M. Proth and C. Chu, A survey of the state-of-the-art of common due date assignment and scheduling research, European Journal of Operational Research, 139(1) (2002), 1–25. [11] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5 (1979), 287–326. [12] L.A. Hall, A.S. Schulz, D.B. Shmoys and J. Wein, Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms, Mathematics of Operations Research, 22(3) (1997), 513–544. [13] M. Hanss, Applied Fuzzy Arithmetic: An Introduction with Engineering Applications, Springer Press, Berlin, 2005. [14] M. Iranpoor, S.M.T. FatemiGhomi and M. Zandieh, Due-date assignment and machine scheduling in a low machine-rate situation with stochastic processing times, Computers & Operations Research, 40(4) (2013), 1100–1108. [15] M. Ji, J.J. Ge, K. Chen and T.C.E. Cheng, Single-machine due-window assignment and scheduling with resource allocation, aging effect, and a deteriorating rate-modifyingactivity, Computers & Industrial Engineering, 66(4) (2013), 952–961. [16] J. Li, K. Sun, D. Xu and H. Li, Single machine due date assignment scheduling problem with customer service level in fuzzy environment, Applied Soft Computing, 10(3) (2010), 849–858. [17] J. Li, X. Yuan, E.S. Lee and D. Xu, Setting due dates to minimize the total weighted possibilistic mean value of the weighted earliness-tardiness costs on a single machine, Computers & Mathematics with Applications, 62(11) (2011), 4126–4139. [18] L. Liu, J. Wang, F. Liu and M. Liu, Single machine due window assignment and resource allocation scheduling problems with learning and general positional effects, Journal of Manufacturing Systems, 43(1) (2017), 1–14. [19] L. Liu, J. Wang and X. Wang, Single machine due-window assignment scheduling with resource-dependent processing times to minimize total resource consumption cost, International Journal of Production Research, 54(4) (2016), 1–10. [20] I.N. Lushchakova, Two machine preemptive scheduling problem with release dates, equal processing times and precedence constraints, European Journal of Operational Research, 171(1) (2006), 107–122. [21] V. Portougal and D. Trietsch, Setting due dates in a stochastic single machine environment, Computers & Operations Research, 33(6) (2006), 1681–1694. [22] M. Queyranne, Structure of a simple scheduling polyhedron, Mathematical Programming, 58(1-3) (1993), 263–285. [23] M. Rasti-Barzoki and S. Hejazi, Pseudo-polynomial dynamic programming for an integrated due date assignment, resource allocation, production, and distribution scheduling model in supply chain scheduling, Applied Mathematical Modelling, 39(12) (2015), 3280–3289. [24] D. Shabtay, Due date assignments and scheduling a single machine with a general earliness/ tardiness cost function, Computers & Operations Research, 35(5) (2008), 1539–1545. [25] D. Shabtay, Y. Itskovich, L. Yedidsion and D. Oron, Optimal due date assignment and resource allocation in a group technology scheduling environment, Computers & Operations Research, 37(12) (2010), 2218–2228. [26] D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times, Discrete Applied Mathematics, 155(13) (2007), 1643–1666. [27] D. Shabtay, G. Steiner, The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times, Annals of Operations Research, 159(1)(2008), 25–40. [28] D. Shabtay and G. Steiner, Two due date assignment problems in scheduling a single machine, Operations Research Letters, 34(6) (2006), 683–691. [29] D. Shabtay, G. Steiner and R. Zhang, Optimal coordination of resource allocation, due date assignment and scheduling decisions, Omega, 65 (2016), 41–54. [30] H. Soroush, Sequencing and due-date determination in the stochastic single machine problem with earliness and tardiness costs, European Journal of Operational Research, 113(2) (1999), 450–468. [31] N. H. Tuong and A. Soukha, Due dates assignment and JIT scheduling with equal-size jobs, European Journal of Operational Research, 205(2) (2010), 280–289. [32] D.L. Yang, C.J. Lai and S.J. Yang, Scheduling problems with multiple due windows assignment and controllable processing times on a single machine, International Journal of Production Economics, 150 (2014), 96–103. [33] Y. Yin, T.C.E. Cheng, C.C. Wu and S.R. Cheng, Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time, Journal of the Operational Research Society, 65(1) (2014), 1–13. [34] Y. Yin, T.C.E. Cheng, D. Xu and C. Wu, Common due date assignment and scheduling with a rate-modifying activity to minimize the due date, earliness, tardiness, hoding and batch delivery cost, Computers & Industrial Engineering, 63(1) (2012), 223–234. [35] Q. Yue and G. Wan, Order schedule with controllable processing times, common due date and processing deadline, Journal of Systems Science and Systems Engineering, 26(2) (2017), 199–218. [36] C. Zhao and H. Tang, Two-machine flow shop scheduling with deteriorating jobs and chain precedence constraints, International Journal of Production Economics, 136(1) (2012), 131– 136. | ||
آمار تعداد مشاهده مقاله: 574 تعداد دریافت فایل اصل مقاله: 287 |