Document Type : Research Paper


1 School of Applied Mathematics, Zhuhai Municipal Key Laboratory of Intelligent Control, Beijing Normal University Zhuhai, Zhuhai 519087, P.R. China

2 School of Science, East China University of Technology, Nanchang 330013, P.R. China

3 School 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.


[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),
[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),
[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),
[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),
[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),
[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–