当前位置：文档库 > 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 2008

Received in revised form 25August 2009Accepted 1September 2009

Available 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@http://www.wendangku.net/doc/0962d91ea76e58fafab0039f.html.tr (C.?zgüven),lozbakir@http://www.wendangku.net/doc/0962d91ea76e58fafab0039f.html.tr (L.?zbak?r),yaseminy@http://www.wendangku.net/doc/0962d91ea76e58fafab0039f.html.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