Scheduling job shop problems with operators with respect to the maximum lateness

被引：3
|
作者：
Benkalai, Imene [1 ]
Rebaine, Djamal [1 ]
Baptiste, Pierre [2 ]
机构：
[1] Univ Quebec Chicoutimi, Dept Informat & Math, Saguenay, PQ G7H 2B1, Canada
[2] Ecole Polytech Montreal, Dept Math & Genie Ind, Montreal, PQ H3T 1J4, Canada
来源：
RAIRO-OPERATIONS RESEARCH | 2020年 / 54卷 / 02期
关键词：
Scheduling; job shop; operators; maximum lateness; SINGLE-MACHINE; ROBOTIC CELLS; ALGORITHMS; COST;
D O I：
10.1051/ro/2019116
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
This paper deals with the problem of assigning operators to jobs, within a free assignment-changing mode, in a job-shop environment subject to a fixed processing sequence of the jobs. We seek an assignment of operators that minimizes the maximum lateness. Within this model, a job needs an operator during the entire duration of its processing. We show that the problem is MATHEMATICAL SCRIPT CAPITAL N & xdca9;P & xdcab;NP$ \mathcal{NP}$-hard when the number of operators is arbitrary and exhibit polynomial time algorithms for the cases involving one and two operators, respectively.
引用
收藏
页码：555 / 568
页数：14
相关论文
共 50 条
  • [1] Minimizing the maximum lateness for scheduling with release times and job rejection
    Kacem, Imed
    Kellerer, Hans
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2024, 48 (03)
  • [2] A heuristic approach for large scale job shop scheduling problems
    Department of Industrial Engineering, Amirkabir University of Technology, P.O. Box 15875-4413, Tehran, Iran
    J. Appl. Sci., 2008, 6 (992-999): : 992 - 999
  • [3] Minimizing the expected maximum lateness for a job shop subject to stochastic machine breakdowns
    Zambrano-Rey, Gabriel Mauricio
    Gonzalez-Neira, Eliana Maria
    Forero-Ortiz, Gabriel Fernando
    Ocampo-Monsalve, Maria Jose
    Rivera-Torres, Andrea
    ANNALS OF OPERATIONS RESEARCH, 2024, 338 (01) : 801 - 833
  • [4] Single machine scheduling to minimize the absolute maximum lateness with shortening job processing times
    Huang, Xue
    JOURNAL OF INFORMATION & OPTIMIZATION SCIENCES, 2012, 33 (06) : 645 - 651
  • [5] New single machine and job-shop scheduling problems with availability constraints
    Mauguière, P
    Billaut, JC
    Bouquard, JL
    JOURNAL OF SCHEDULING, 2005, 8 (03) : 211 - 231
  • [6] New Single Machine and Job-Shop Scheduling Problems with Availability Constraints
    Ph. Mauguière
    J.-C. Billaut
    J.-L. Bouquard
    Journal of Scheduling, 2005, 8 : 211 - 231
  • [7] Mathematical Models of Flow Shop and Job Shop Scheduling Problems
    Seda, Milos
    PROCEEDINGS OF WORLD ACADEMY OF SCIENCE, ENGINEERING AND TECHNOLOGY, VOL 25, 2007, 25 : 122 - 127
  • [8] Scheduling Data Gathering with Maximum Lateness Objective
    Berlinska, Joanna
    PARALLEL PROCESSING AND APPLIED MATHEMATICS (PPAM 2017), PT II, 2018, 10778 : 135 - 144
  • [9] Hybrid flow shop scheduling with precedence constraints and time lags to minimize maximum lateness
    Botta-Genoulaz, V
    INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2000, 64 (1-3) : 101 - 111
  • [10] A Genetic Algorithm for job shop scheduling problems with alternate routing
    Hussain, MF
    Joshi, SB
    1998 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS, VOLS 1-5, 1998, : 2225 - 2230
12345