Minimizing the number of switch instances on a flexible machine in polynomial time

被引：14

作者：

Adjiashvili, David ^{[1
]}

Bosio, Sandro ^{[1
]}

Zemmer, Kevin ^{[1
]}

机构：

[1] Swiss Fed Inst Technol, Inst Operat Res, Zurich, Switzerland

来源：

OPERATIONS RESEARCH LETTERS | 2015年 / 43卷 / 03期

关键词：

Scheduling; Tool switching; Combinatorial algorithm; Manufacturing; Flexible machine; MANUFACTURING MACHINE; MINIMIZATION; MODELS;

D O I：

10.1016/j.orl.2015.04.001

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We revisit the tool switching problem on a flexible manufacturing machine. We present a polynomial algorithm for the problem of finding a switching plan that minimizes the number of tool switch instances on the machine, given a fixed job sequence. We prove tight hardness results for the variable sequence case with the same objective function, as well as a new objective function naturally arising in multi-feeder mailroom inserting systems. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：317 / 322

页数：6

共 13 条

[1] A STUDY OF REPLACEMENT ALGORITHMS FOR A VIRTUAL-STORAGE COMPUTER [J].

BELADY, LA .

IBM SYSTEMS JOURNAL, 1966, 5 (02) :78-&

[2] Production planning problems in printed circuit board assembly [J].

Crama, Y ;

van de Klundert, J ;

Spieksma, FCR .

DISCRETE APPLIED MATHEMATICS, 2002, 123 (1-3) :339-361

[3]

Crama Y., 1994, International Journal of Flexible Manufacturing Systems, V6, P33, DOI 10.1007/BF01324874

[4] A COLUMN GENERATION APPROACH TO JOB GROUPING FOR FLEXIBLE MANUFACTURING SYSTEMS [J].

CRAMA, Y ;

OERLEMANS, AG .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 78 (01) :58-80

[5]

Crama Y., 1996, 019 METEOR MAASTR U

[6] The tool switching problem revisited [J].

Crama, Yves ;

Moonen, Linda S. ;

Spieksma, Frits C. R. ;

Talloen, Ellen .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 182 (02) :952-957

[7] HAMILTON PATHS IN GRID GRAPHS [J].

ITAI, A ;

PAPADIMITRIOU, CH ;

SZWARCFITER, JL .

SIAM JOURNAL ON COMPUTING, 1982, 11 (04) :676-686

[8]

Miltze T., 2014, EUROPEAN J OPER RES, V236, P37

[9] OPTIMIZATION, APPROXIMATION, AND COMPLEXITY CLASSES [J].

PAPADIMITRIOU, CH ;

YANNAKAKIS, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1991, 43 (03) :425-440

[10] MODELING A TOOL SWITCHING PROBLEM ON A SINGLE NC-MACHINE [J].

PRIVAULT, C ;

FINKE, G .

JOURNAL OF INTELLIGENT MANUFACTURING, 1995, 6 (02) :87-94

← 1 2 →