Please enable JavaScript.

Coggle requires JavaScript to display documents.

Теория расписаний - Coggle Diagram

- - - - Online Over Time
        
        Minimize the Total Completion Time
        
        с прерываниями
        
        shortest remaining processing time algorithm (SRPT)
        
        at any time processes an available job that has the least processing left
        
        без прерываний
        
        delayed SPT
        
        an ordering by increasing processing requirements, but we do not know what jobs are arriving in the future and we do not know how to wait for something smaller.
        
        shifted SPT algorithm
        
        shortest processing time algorithm (SPT)
        
        if the machine is idle, choose from among the available jobs the one with the shortest processing time
        
        alpha-scheduler
        
        ONE-MACHINE
        
        Minimizing Maximum delivery time
        
        с прерываниями
        
        largest available delivery time algorithm (LADT)
        
        без прерываний
        
        largest delivery time algorithm (LDT)
        
        delayed LDT
        
        As soon as the machine becomes available for processing, choose an available job with highest priority, and schedule it if its processing requirement is not too large. Otherwise, postpone the start of this job.
  - - - Makespan
        
        без прерываний
        
        List Scheduling
        
        always assigns the current job to the machine where it can be started to process the earliest, that is, the machine with the smallest current load
        
        Algorithm Random
        
        с прерываниями
        
        Algorithm Preemptive
    - - Makespan
        
        без прерываний
        
        Longest Processing Time first (online LPT)
        
        The on-line LPT algorithm can be described as follows. At any time a machine becomes available for processing, schedule an available job with the largest processing requirement. If no jobs are available, then wait until the next arrival.
        
        Shmoys, Wein & Williamson [1995]
        
        This method iteratively uses the off-line algorithm on the set of available jobs. Once all the jobs that have been scheduled in the last iteration have been completed, the method uses the off-line algorithm on the jobs that have arrived during this period, and this process is repeated
        
        с прерываниями
        
        [Hong & Leung, 1992]
      - Minimize the Total Completion Time
        
        С прерываниями
        
        multi-machine generalization oft he single-machine algorithm SRPT
        
        always processes the m jobs with the shortest remaining processing requirement
      - Minimizing Maximum delivery time
        
        с прерываниями
        
        [Labetoulle, Lawler, Lenstra & Rinnooy Kan, 1984]
        
        без прерываний
        
        largest delivery time algorithm (LDT)
        
        if a machine is idle, choose from among the available jobs the one with the largest delivery time.
  - - - Flow shop
        
        Все задачи проходят одни и те же машины в фиксированном порядке
      - Job Shop
        
        для каждой задачи имеется своё упорядоченное подмножество машин (маршрут), на которых оно должно обслуживаться в заданном порядке
      - Open shop
        
        Задача может выполняться в любом порядке
- - - - the total size of all jobs
    - - the largest processing time or largest size job
    - - the value of the smallest makespan
    - - describes that jobs arrive in order of non-increasing sizes
    - - It is known in advance that last job has the largest processing time
    - - a storage unit of finite length