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 条
  • [1] Aldowaisan T(2003)New heuristics for no-wait flowshops to minimize makespan Comput Oper Res 30 1219-1231
  • [2] Allahverdi A(1991)A computational study of the job-shop problem ORSA Comput 3 149-156
  • [3] Applegate D(1979)Disjunctive programming Ann Discrete Math 5 3-51
  • [4] Cook W(1998)Guided local search with shifting bottleneck for job-shop- scheduling Manage Sci 44 262-275
  • [5] Balas E(1996)The job-shop-scheduling-problem: conventional and new solution techniques Eur J Oper Res 93 1-33
  • [6] Balas E(1994)A branch and bound algorithm for the job-shop- scheduling-problem Discrete Appl Math 49 107-127
  • [7] Vazacopoulos A(1978)Ordonnancements à contraintes disjonctives R.A.I.R.O. Recherche opérationnelle/Oper Res 12 333-351
  • [8] Blazewicz J(1989)Tabu search – part i ORSA J Comput 1 190-206
  • [9] Domschke W(1990)Tabu search – part ii ORSA J Comput 2 4-32
  • [10] Pesch E(2000)Sequencing of jobs in some production system Eur J Oper Res 125 535-550
123456