No-wait Job Shop Scheduling: Tabu Search and Complexity of Subproblems

被引：0
作者：
Christoph J. Schuster
机构：
[1] LOG-PW Solutions for Planning and Warehouse Management,Bayer Business Services
来源：
Mathematical Methods of Operations Research | 2006年 / 63卷
关键词：
Scheduling; Job shop; No-wait; Decomposition; Complexity; Tabu search; Flow shop; 90B35 (deterministic scheduling theory);
D O I：
暂无
中图分类号：
学科分类号：
摘要：
This paper deals with the no-wait job shop problem with a makespan objective. We present some new theoretical properties on the complexity of subproblems associated with a well-known decomposition approach. Justified by the complexity results, we implement a fast tabu search algorithm for the problem at hand. It is extensively tested on known benchmark instances and compares favorably to the best existing algorithms for the no-wait job shop as well as the no-wait flow shop.
引用
收藏
页码：473 / 491
页数：18
相关论文
共 55 条
  • [21] Lenstra JK(2000)Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing. Eur J Oper Res 126 131-151
  • [22] Rinnooy Kan AHG(1994)A no-wait flowshop scheduling heuristic to minimize makespan J Oper Res Soc 45 472-478
  • [23] Guinet A(1973)A scheduling-problem Oper Res Q 24 441-446
  • [24] Legrand M(1995)A genetic algorithm for flowshop sequencing Comput Oper Res 22 5-13
  • [25] Hall NG(1979)Complexity of scheduling shops with no-wait in process Math Oper Res 4 448-457
  • [26] Sriskandarajah C(2003)Approximative procedures for no-wait job shop scheduling Oper Res Lett 31 308-318
  • [27] Heller J(1992)New search spaces for sequencing instances with application to job shop scheduling Manage Sci 38 1495-1509
  • [28] Jain A(1972)Solution of the flowshop scheduling-problem with no intermediate queues Oper Res 20 689-697
  • [29] Meeran S(2004)Inapproximability results for no-wait job shop scheduling Oper Res Lett 32 320-325
  • [30] Lenstra JK(undefined)undefined undefined undefined undefined-undefined
123456