Designing an efficient bi-criteria iterated greedy heuristic for simultaneous order scheduling and resource allocation: a balance between cost and lateness measures

详细信息    查看全文

• 作者：Hadi Mokhtari
• 关键词：Iterated greedy heuristic ; Multiple criteria decision making ; Resource allocation ; Order scheduling
• 刊名：Neural Computing & Applications
• 出版年：2015
• 出版时间：July 2015
• 年：2015
• 卷：26
• 期：5
• 页码：1085-1101
• 全文大小：1,232 KB
• 参考文献：1.Pfund M, Fowler JW, Gupta JND (2004) A survey of algorithms for single and multi-objective unrelated parallel-machine deterministic scheduling problems. J Chin Inst Ind Eng 21(3):230鈥?41
  2.Pinedo M (1995) Scheduling theory, algorithms, and systems. Prentice Hall, NJMATH
  3.Guinet A (1993) Scheduling sequence-dependent jobs on identical parallel machines to minimize completion time criteria. Int J Prod Res 31:1579鈥?594View Article
  4.Franca P, Gendreau M, Laporte G, Mnller F (1996) A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times. Int J Prod Econ 43:79鈥?9View Article
  5.Lee Y, Pinedo M (1997) Scheduling jobs on parallel machines with sequence dependent setup times. Eur J Oper Res 100:464鈥?74MATH View Article
  6.Kurz M, Askin R (2001) Heuristic scheduling of parallel machines with sequence dependent set-up times. Int J Prod Res 39:3747鈥?769MATH View Article
  7.Gendreau M, Laporte G, Morais-Guimaraes E (2001) A divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times. Eur J Oper Res 133:183鈥?89MATH View Article
  8.Hurink J, Knust S (2001) List scheduling in a parallel machine environment with precedence constraints and setup times. Oper Res Lett 29:231鈥?39MATH MathSciNet View Article
  9.Eom D, Shin H, Kwun I, Shim J, Kim S (2002) Scheduling jobs on parallel machines with sequence dependent family set-up times. Int J Adv Manuf Technol 19:926鈥?32View Article
  10.Lin C-H, Liao C-J (2004) Makespan minimization subject to flowtime optimality on identical parallel machines. Comput Oper Res 31(10):1655鈥?666MATH MathSciNet View Article
  11.Dunstall S, Wirth A (2005) Heuristic methods for the identical parallel machine flowtime problem with set-up times. Comput Oper Res 32:2479鈥?491MATH View Article
  12.Tahar D, Yalaoui F, Chu C, Amodeo L (2006) A linear programming approach for identical parallel machine scheduling with job splitting and sequence dependent setup times. Int J Prod Econ 99:63鈥?3View Article
  13.Anghinolfi D, Paolucci M (2007) Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach. Comput Oper Res 34:3471鈥?490MATH MathSciNet View Article
  14.Rocha ML, Ravetti MG, Mateus GR, Pardalos PM (2007) Solving parallel machines scheduling problems with sequence-dependent setup times using variable neighborhood search. IMA J Manag Math 18:101鈥?15MATH MathSciNet View Article
  15.Shim S-O, Kim Y-D (2007) Scheduling on parallel identical machines to minimize total tardiness. Eur J Oper Res 177(1):135鈥?46MATH MathSciNet View Article
  16.Biskup D, Herrmann J, Gupta JND (2008) Scheduling identical parallel machines to minimize total tardiness. Int J Prod Econ 115(1):134鈥?42View Article
  17.Tanaka S, Araki M (2008) A branch-and-bound algorithm with Lagrangian relaxation to minimize total tardiness on identical parallel machines. Int J Prod Econ 113(1):446鈥?58View Article
  18.Pfund M, Fowler J, Gadkari A, Chen Y (2008) Scheduling jobs on parallel machines with setup times and ready times. Comput Ind Eng 54:764鈥?82View Article
  19.Yu A-Q, Gu X-S (2008) Coupled transiently chaotic neural network approach for identical parallel machine scheduling. Zidonghua Xuebao Acta Autom Sin 34(6):697鈥?01MathSciNet View Article
  20.Nessah R, Yalaoui F, Chu C (2008) A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates. Comput Oper Res 35(4):1176鈥?190MATH MathSciNet View Article
  21.Driessel R, M枚nch L (2011) Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times. Comput Ind Eng 61(2):336鈥?45View Article
  22.Hu X, Bao J-S, Jin Y (2010) Minimizing make span on parallel machines with precedence constraints and machine eligibility restrictions. Int J Prod Res 48(6):1639鈥?651MATH View Article
  23.McCarthy BL, Liu J (1993) A new classification for flexible manufacturing systems. Int J Prod Res 31(2):299鈥?09View Article
  24.Atan MO, Selim Akturk M (2008) Single CNC machine scheduling with controllable processing times and multiple due dates. Int J Prod Res 46(21):6087鈥?111MATH View Article
  25.Karimi-Nasab M, Fatemi Ghomi SMT (2012) Multi-objective production scheduling with controllable processing times and sequence-dependent setups for deteriorating items. Int J Prod Res 50(24):7378鈥?400View Article
  26.Nearchou AC (2010) Scheduling with controllable processing times and compression costs using population-based heuristics. Int J Prod Res 48(23):7043鈥?062MATH View Article
  27.Niu G, Sun S, Lafon P, Zhang Y, Wang J (2012) Two decompositions for the bicriteria job-shop scheduling problem with discretely controllable processing times. Int J Prod Res 50(24):7415鈥?427View Article
  28.Yildiz S, Akturk MS, Karasan OE (2011) Bicriteria robotic cell scheduling with controllable processing times. Int J Prod Res 49(2):569鈥?83MATH View Article
  29.Nowicki E, Zdrzalka S (1990) A survey of results for sequencing problems with controllable processing times. Discrete Appl Math 26:271鈥?87MATH MathSciNet View Article
  30.Shabtay D, Steiner G (2007) A survey of scheduling with controllable processing times. Discrete Appl Math 155(13):1643鈥?666MATH MathSciNet View Article
  31.Vickson RG (1980) Two single-machine sequencing problems involving controllable processing times. AIIE Trans 12:258鈥?62MathSciNet View Article
  32.Janiak A (1985) Time-optimal control in a single machine problem with resource constraints. Automatica 22:745鈥?47View Article
  33.Janiak A (1987) One-machine scheduling with allocation of continuously-divisible resource and with no precedence constraints. Kybernetika 23:289鈥?93MATH MathSciNet
  34.Janiak A, Kovalyov MY (1996) Single machine scheduling subjective to deadlines and resource dependent processing times. Eur J Oper Res 94:284鈥?91MATH View Article
  35.Iwanowski D, Janiak A (2002) Optimal resource allocation for single machine scheduling problems with time and resource dependent processing times. Syst Sci 28(2):85鈥?4MathSciNet
  36.Hoogeveen H, Woeginger GJ (2002) Some comments on sequencing with controllable processing times. Computing 68:181鈥?92MATH MathSciNet View Article
  37.Kaspi M, Shabtay D (2004) Convex resource allocation for minimizing the makespan in a single machine with job release dates. Comput Oper Res 31:1481鈥?489MATH MathSciNet View Article
  38.Shabtay D, Kaspi M (2004) Minimizing the total weighted flow time in a single machine with controllable processing times. Comput Oper Res 31:2279鈥?289MATH MathSciNet View Article
  39.Kaspi M, Shabtay D (2006) A bicriterion approach to time/cost trade-offs in scheduling with convex resource-dependent job processing times and release dates. Comput Oper Res 33(10):3015鈥?033MATH View Article
  40.Cheng TCE, Janiak A, Kovalyov MY (2001) Single machine batch scheduling with resource dependent setup and processing times. Eur J Oper Res 135:177鈥?83MATH MathSciNet View Article
  41.Janiak A, Kovalyov MY, Portmann MC (2005) Single machine group scheduling with release dependent setup and processing times. Eur J Oper Res 162:112鈥?21MATH MathSciNet View Article
  42.Ng CT, Cheng TCE, Janiak A, Kovalyov MY (2005) Group scheduling with controllable setup and processing times: minimizing total weighted completion time. Ann Oper Res 133:163鈥?74MATH MathSciNet View Article
  43.Choi B-C, Yoon S-H, Chung S-J (2007) Single machine scheduling problem with controllable processing times and resource dependent release times. Eur J Oper Res 181:645鈥?53MATH MathSciNet View Article
  44.Xu K, Feng Z, Jun K (2010) A tabu-search algorithm for scheduling jobs with controllable processing times on a single machine to meet due-dates. Comput Oper Res 37(11):1924鈥?938MATH MathSciNet View Article
  45.Choi BC, Leung JY-T, Pinedo ML (2010) Complexity of a scheduling problem with controllable processing times. Oper Res Lett 38:123鈥?26MATH MathSciNet View Article
  46.Wang D, Wang M-Z, Wang J-B (2010) Single-machine scheduling with learning effect and resource-dependent processing times. Comput Ind Eng 59(3):458鈥?62View Article
  47.Wei C-M, Wang J-B, Ji P (2012) Single-machine scheduling with time-and-resource-dependent processing times. Appl Math Model 36:792鈥?98MATH MathSciNet View Article
  48.J贸zefowska J, Mika M, Walig贸ra G, W臋glarz J (2002) Multi-mode resource-constrained project scheduling problem with discounted positive cash flows鈥攕imulated annealing vs. tabu search. Found Comput Decis Sci 27:97鈥?14
  49.Jansen K, Mastrolilli M (2004) Approximation schemes for parallel machine scheduling problems with controllable processing times. Comput Oper Res 31:1565鈥?581MATH MathSciNet View Article
  50.Al-Fawzan MA, Haouari M (2005) A bi-objective model for robust resource-constrained project scheduling. Int J Prod Econ 96:175鈥?87View Article
  51.Li K, Shi Y, Yang S-L, Cheng B-Y (2011) Parallel machine scheduling problem to minimize the makespan with resource dependent processing times. Appl Soft Comput J 11(8):5551鈥?557View Article
  52.Janiak A (1988) General flow-shop scheduling with resource constraints. Int J Prod Res 26:1089鈥?103MATH View Article
  53.Shabtay D, Kaspi M, Steiner G (2007) The no-wait two-machine flow shop scheduling problem with convex resource-dependent processing times. IIE Trans Inst Ind Eng 39(5):539鈥?57
  54.Mokhtari H, Abadi INK, Cheraghalikhani A (2011) A multi-objective flow shop scheduling with resource-dependent processing times: trade-off between makespan and cost of resources. Int J Prod Res 49(19):5851鈥?875View Article
  55.Mokhtari H, Abadi INK, Zegordi SH (2011) Production capacity planning and scheduling in a no-wait environment with controllable processing times: an integrated modeling approach. Expert Syst Appl 38(10):12630鈥?2642View Article
  56.Jansen K, Mastrolilli M, Solis-Oba R (2005) Approximation schemes for job shop scheduling problems with controllable processing times. Eur J Oper Res 167(2005):297鈥?19MATH MathSciNet View Article
  57.Ying K-C, Lin S-W, Huang C-Y (2009) Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic. Expert Syst Appl 36:7087鈥?092View Article
  58.Ying K-C, Lin S-W, Huang C-Y (2009) Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic. Expert Syst Appl 36(3 PART 2):7087鈥?092View Article
  59.Ying K-C, Cheng H-M (2010) Dynamic parallel machine scheduling with sequence-dependent setup times using an iterated greedy heuristic. Expert Syst Appl 37:2848鈥?852View Article
  60.Chang F, Wu J-S, Lee C-N, Shen H-C (2014) Greedy-search-based multi-objective genetic algorithm for emergency logistics scheduling. Expert Syst Appl 41:2947鈥?956View Article
  61.Balin S (2011) Non-identical parallel machine scheduling using genetic algorithm. Expert Syst Appl 38:6814鈥?821View Article
  62.Mart铆nez P, Eliceche AM (2011) Bi-objective minimization of environmental impact and cost in utility plants. Comput Chem Eng 35(8):1478鈥?487View Article
  63.Ruiz R, St眉tzle T (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 177:2033鈥?049MATH View Article
  64.Ruiz R, St眉tzle T (2008) An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives. Eur J Oper Res 187(3):1143鈥?159MATH View Article
  65.Cheng H-M, Ying K-C (2011) Minimizing makespan in a flow-line manufacturing cell with sequence dependent family setup times. Exp Syst Appl 38:15517鈥?5522View Article
  66.Ying K-C (2008) Solving non-permutation flowshop scheduling problems by an effective iterated greedy heuristic. Int J Adv Manuf Technol 38(3鈥?):348鈥?54View Article
  67.Zhi Y, Armin F, Henning H, Prasanna B, Thomas S, Michael S (2008) Iterated greedy algorithms for a real-world cyclic train scheduling problem. Hybrid metaheuristics. Springer, Berlin, pp 102鈥?16
  68.Hwang & Young-Jou (1994) Fuzzy multiple objective decision making: methods and applications. Springer, BerlinMATH
  69.Holland J (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor
  
• 作者单位：Hadi Mokhtari (1)
  
  1. Department of Industrial Engineering, Faculty of Engineering, University of Kashan, Kashan, Iran
  
• 刊物类别：Computer Science
• 刊物主题：Simulation and Modeling
  
• 出版者：Springer London
• ISSN：1433-3058

文摘

In this paper, an iterated greedy (IG) heuristic as an intelligent decision-making algorithm is designed for solving a general variant of order scheduling problem with resource allocation. It is assumed that the processing times can be controlled by allocation of a non-renewable common resource, as it is the case in many real-world processes. In order to jointly minimize the number of late orders and the amount of resources consumed, the global criterion as a multiple criteria decision-making method is adapted. Furthermore, a two-layered IG heuristic is devised as solution method. IG heuristic employs a simple but efficient principle and is easy to implement with high capability of evolutionary performance. In suggested IG, a set of solutions is produced by iterating over a greedy construction heuristic by using both destruction and construction functions and then an improving local search is implemented to further enhance the quality of solutions. The simulation experiments show that the proposed IG heuristic is an effective tool in producing high-qualified solutions with respect to the traditional algorithms.