SCHEDULING SEQUENCE-DEPENDENT JOBS ON IDENTICAL PARALLEL MACHINES TO MINIMIZE COMPLETION-TIME CRITERIA

被引：64

作者：

GUINET, A

机构：

[1] Laboratoire d'lnformatique des Systémes de Production Industries, Universite Claude Bernard, Villeurbanne, 69622, Bât. 710, Lyon 1

来源：

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH | 1993年 / 31卷 / 07期

关键词：

D O I：

10.1080/00207549308956810

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

We consider the problem of scheduling sequence-dependent jobs on identical parallel machines. Each job has to be processed without interruption on one of the machines. A machine changeover-time must be respected between job processing on each machine. This changeover time is dependent on the job sequence. Our objective is to minimize the maximum completion time of the jobs or the mean completion time of the jobs. This problem is a vehicle routeing problem and is NP hard. We propose an assignment algorithm to solve it. Our heuristic is an extension of the Hungarian method to the multiple use of resources and has been developed during past years to solve routeing problems. This paper models the scheduling problem, presents the solution tool, and shows the heuristic result quality for 24 problem sizes.

引用

页码：1579 / 1594

页数：16

共 24 条

[1]

Bruno J., Coffman E.G., Sethi R., Scheduling independent tasks to reduce mean finishing time, Communications of the ACM, 17, 7, pp. 382-387, (1974)

[2]

Clarke G., Wright J.W., Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12, pp. 568-581, (1964)

[3]

Dogramaci A., Surkis J., Evaluation of a heuristic for scheduling independent jobs on parallel identical processors, Management Science, 25, 12, pp. 1208-1216, (1979)

[4]

Frenk J., Rinnooy Kan A., The asymptotic optimality of the LPT rule, Mathematics of Operations Research, 12, pp. 241-254, (1987)

[5]

Geoffrion A.M., Graves G.W., Scheduling parallel production lines with changeover costs: Practical application of a quadratic assignment fLP approach, Operations Research, 24, 4, pp. 595-610, (1976)

[6]

Graham R.L., Bounds on multiprocessing timing anomalies, Siam Journal of Applied Mathematics, 17, pp. 416-429, (1969)

[7]

Guinet A., Transports industriels routiers, un probleme d'affectation avec reemploi sous contraintes, Revue D'automatique D'informatique Et De Recherche Operationnelle, 18, 4, pp. 353-379, (1984)

[8]

Guinet A., Ordonnancement d'une fonderie de fontes, Revue D'automatique D'informatique Et De Recherche Operationnelle, 22, 5, pp. 471-488, (1988)

[9]

Guinet A., Des Tournees Routieres Assistees Par Ordinateur, (1989)

[10]

Guinet A., Textile production systems: A succession of non-identical parallel processor shops, Journal of Operational Research Society, 42, 8, pp. 655-671, (1991)

← 1 2 3 →