当前位置：文档库 > Mathematical models for job-shop scheduling problems with routing and process plan flexibility

Mathematical models for job-shop scheduling problems with routing and process plan ﬂexibility

Cemal Özgüven a,*,Lale Özbakır b ,Yasemin Yavuz a

a

Erciyes University,Faculty of Economics and Administrative Sciences,Department of Business,38039Kayseri,Turkey b Erciyes University,Faculty of Engineering,Department of Industrial Engineering,38039Kayseri,Turkey

a r t i c l e i n f o Article history:Received 31October 2008Received in revised form 25August 2009Accepted 1September 2009Available online 4September 2009Keywords:Job-shop scheduling Routing ﬂexibility Process plan ﬂexibility Mixed-integer programming

a b s t r a c t

As a result of rapid developments in production technologies in recent years,ﬂexible job-

shop scheduling problems have become increasingly signiﬁcant.This paper deals with two

NP-hard optimization problems:ﬂexible job-shop scheduling problems (FJSPs)that

encompass routing and sequencing sub-problems,and the FJSPs with process plan ﬂexibil-

ity (FJSP-PPFs)that additionally include the process plan selection sub-problem.The study

is carried out in two steps.In the ﬁrst step,a mixed-integer linear programming model

(MILP-1)is developed for FJSPs and compared to an alternative model in the literature

(Model F)in terms of computational efﬁciency.In the second step,one other mixed-integer

linear programming model,a modiﬁcation of MILP-1,for the FJSP-PPFs is presented along

with its computational results on hypothetically generated test problems.

Ó2009Elsevier Inc.All rights reserved.1.Introduction

Scheduling may broadly be deﬁned as the allocation of resources to tasks over time in such a way that a predeﬁned per-formance measure is optimized.From the viewpoint of production scheduling,the resources and tasks are commonly re-ferred to as machines and jobs and the commonly used performance measure is the completion times of jobs.This problem has been extensively researched since the early 1950’s.A comprehensive survey of literature on scheduling prob-lems can be found in Graves [1],Lawler et al.[2],and Lee et al.[3].

The classical job-shop scheduling problem (JSP)consists of a set of independent jobs,each having its own processing or-der through a set of machines.Each job has an ordered set of operations,each of which must be processed on a predeﬁned machine.The problem,known to be strongly NP-hard,is to sequence operations on the machines so that the maximum com-pletion time over all jobs (C max )is minimized.Considerable research has been devoted to this problem in the literature.An overview of history and main techniques used along with their reported results on the available benchmarking problems for JSP can be found in Jain and Meeran [4].

The JSP assumes only one available machine for each operation and one feasible process plan (operation sequence)for each job.It is common,however,in real-world scheduling problems to have a wider space for choices.Typically,in a man-ufacturing setting there are choices to be made in scheduling from among alternative machines on which to perform an operation or from among alternative process plans of a job through a factory [5].This paper considers two extensions to the JSP,i.e.,routing ﬂexibility and process plan ﬂexibility .The former implies the availability of alternative machines for each operation,and the latter the availability of alternative process plans for each job.

0307-904X/$-see front matter Ó2009Elsevier Inc.All rights reserved.

doi:10.1016/j.apm.2009.09.002*Corresponding author.Tel.:+903524374901/30150;fax:+903524375239.

E-mail addresses:cozguven@erciyes.edu.tr (C.Özgüven),lozbakir@erciyes.edu.tr (L.Özbakır),yaseminy@erciyes.edu.tr (Y.Yavuz).

Applied Mathematical Modelling 34(2010)1539–1548

Contents lists available at ScienceDirect

Applied Mathematical Modelling

j o u r n a l h o m e p a g e :w w w.e l s e v i e r.c o m /l o c a t e /a p m