In recent years, due window assignment scheduling problems deriving from just-in-time supply chain management have been studied extensively. However, precedence constraints and uncertain processing times of jobs are rarely involved simultaneously in the studies. In this paper, a single machine due window assignment scheduling problem with uncertain processing times, precedence constraints and due window size constraints is investigated, in which the processing times of jobs are presented by fuzzy numbers. The objective is to minimize the mean value of the total earliness-tardiness penalties. An optimal polynomial time algorithm is proposed for the problem when there are no precedence constraints among jobs. Note that the problem with general precedence constraints is NP-hard. An efficient 2-approximation algorithm is proposed for the general constraint problem based on linear programming relaxation. The experimental results show that the proposed methods are effective and promising.
BaykasǒsgluA., M.Gkǒen and Z.D.Unutmaz, New approaches todue date assignment in job shops, European Journal of Operational Research187(1) (2008), 31–45.
2.
JaniakA., KwiatkowskiT. and LichtensteinM., Scheduling problemswith a common due window assignment: A survey, International Journal of Applied Mathematics and Computer Science23(1) (2013), 231–241.
3.
JaniakA., KovalyovM. and MarekM., Soft due window assignment andscheduling on parallel machines, IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans37(5) (2007), 614–620.
4.
WongB. and LaiV., A survey of the application of fuzzy set theoryin production and operations management: 1998-2009, International Journal of Production Economics129(1) (2011), 157–168.
5.
CarlssonC. and FullérR., On possibilistic mean value and variance of fuzzy numbers, Fuzzy Sets and Systems122(2) (2001), 315–326.
6.
YangD., LaiC. and YangS., Scheduling problems with multiple duewindows assignment and controllable processing times on a single machine,, International Journal of Production Economics150 (2014), 96–103.
7.
GerstlE. and MosheiovG., An improved algorithm algorithm fordue-window assignment on parallel identical machines with unit-timejobs, Information Processing Letters113(19-21) (2013), 754–759.
8.
GerstlE. and MosheiovG., Due-window assignment with identical jobs on parallel uniform machines, European Journal of Operational Research229(1) (2013), 41–47.
9.
LushchakovaI.N., Two machine preemptive scheduling problem with release dates, equal processing times and precce constraints, European Journal of Operational Research171(1) (2006), 107–122eden.
10.
LiJ., SunK. and LiD.H., Single machine due date assignment scheduling problem with customer service level in fuzzy environment, Applied Soft Computing10(3) (2010), 849–858.
11.
LiJ., YuanX., LeeE.S. and XuD., Setting due dates to minimize the total weighted possibilistic mean value of the weighted earliness? tardiness costs on a single machine, Computers and Mathematics with Applications62(11) (2011), 4126–4139.
12.
LeungJ.Y.-T., Introduction and notation in: J.Y.-T.Leung (Ed.), Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman & Hall, CRC, Boca Raton, 2004(Chapter 1).
13.
BakerK.R., Minimizing earliness and tardiness costs in stochasticscheduling, European Journal of Operational Research236(2) (2014), 445–452.
14.
AdolphsonL., Sinle machine job sequencing with precceconstraints, SIAM Journal on Computing6(1) (1977), 40–54.
15.
HallL., SchulzA., ShmoysD. and WeinJ., Scheduling to minimize average completion time: Off-line and On-line approximation algorithms, Mathematics of Operations Research22(3) (1997), 513–544.
16.
LiuL., WangJ., LiuF. and LiuM., Single machine due window assignment and resource allocation scheduling problems with learning and general positional effects, Journal of Manufacturing Systems43(1) (2017), 1–14.
17.
HanssM., Applied Fuzzy Arithmetic: An Introduction with Engineering Applications, Springer, Berlin, 2005.
18.
IranpoorM., FatemiGhomiS.M.T. and ZandiehM., Due-date assignment and machine scheduling in a low machine-rate situation with stochastic processing times, Computers & Operations Research40(4) (2013), 1100–1108.
19.
QueyranneM., Structure of a simple scheduling polyhedron, Mathematical Programming58(1-3) (1993), 263–285.
20.
GrahamR.L., LawlerE.L., LenstraJ.K. and RinnooyA.H.G., Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics5 (1979), 287–326.
21.
SlowińskiR., HapkeM., Scheduling Under Fuzziness, Physica-Verlag, Heidelberg, 2000.
22.
ChengT.C.E., YuanJ.J. and YangA.F., Scheduling a batch processing machine subject to precce constraints, release dates and identical processing times, Operations & Research32(4) (2005), 849–859.
23.
ChengT.C.E., YangS. and YangD., Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and adeteriorating maintenance activity, International Journal of Production Economics135(1) (2012), 154–161.
24.
GordonV., ProthJ. and ChuC., A survey of the state-of-the-art ofcommon due date assignment and scheduling research, European Journal of Operational Research139(1) (2002), 1–25.
25.
PortougalV. and TrietschD., Setting due dates in a stochastic single machine environment, Computers & Operations Research33(6) (2006), 1681–1694.
26.
YeungW., ChoiT. and ChengT.C.E., Optimal scheduling of asingle-supplier single-manufacturer supply chain with common duewindows, IEEE Transactions on Automatic Control55(12) (2010), 2767–2777.
27.
YinY., ChengT.C.E., HsuC. and WuC., Single-machine batch delivery scheduling with an assignable common due window, Omega41(2) (2013), 216–225.
