文档库

最新最全的文档下载
当前位置:文档库 > 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 flexibility

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

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 flexibility Process plan flexibility Mixed-integer programming

a b s t r a c t

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

shop scheduling problems have become increasingly significant.This paper deals with two

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

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

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

is carried out in two steps.In the first 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 efficiency.In the second step,one other mixed-integer

linear programming model,a modification 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 defined as the allocation of resources to tasks over time in such a way that a predefined 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 predefined 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 flexibility and process plan flexibility .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).

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 flexibility

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