Peha, 1995 - Google Patents

Heterogeneous-criteria scheduling: minimizing weighted number of tardy jobs and weighted completion time

Peha, 1995

View PDF
Document ID
13207770393057849910
Author
Peha J
Publication year
Publication venue
Computers & operations research

External Links

Snippet

In this paper, a novel O (N2) algorithm is presented to minimize the weighted number of tardy jobs with unit processing times, integer ready times and deadlines, and M homogeneous parallel machines, where N is the number of jobs to be scheduled. wi is the …
Continue reading at kilthub.cmu.edu (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G06F9/46—Multiprogramming arrangements
    • G06F9/48—Programme initiating; Programme switching, e.g. by interrupt
    • G06F9/4806—Task transfer initiation or dispatching
    • G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
    • G06F9/4881—Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
    • G06F9/4887—Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues involving deadlines, e.g. rate based, periodic
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems
    • H04L12/56—Packet switching systems
    • H04L12/5693—Queue scheduling in packet switching networks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems
    • H04L12/56—Packet switching systems
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06Q—DATA PROCESSING SYSTEMS OR METHODS, SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL, SUPERVISORY OR FORECASTING PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL, SUPERVISORY OR FORECASTING PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/10—Office automation, e.g. computer aided management of electronic mail or groupware; Time management, e.g. calendars, reminders, meetings or time accounting
    • G06Q10/109—Time management, e.g. calendars, reminders, meetings, time accounting
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic regulation in packet switching networks
    • H04L47/50—Queue scheduling
    • H04L47/56—Delay aware scheduling
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06Q—DATA PROCESSING SYSTEMS OR METHODS, SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL, SUPERVISORY OR FORECASTING PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL, SUPERVISORY OR FORECASTING PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management, e.g. organising, planning, scheduling or allocating time, human or machine resources; Enterprise planning; Organisational models

Similar Documents

Publication Publication Date Title
Peha Heterogeneous-criteria scheduling: minimizing weighted number of tardy jobs and weighted completion time
Zhao et al. A window protocol for transmission of time-constrained messages
US5247677A (en) Stochastic priority-based task scheduler
Peha et al. Evaluating scheduling algorithms for traffic with heterogeneous performance objectives
US6477144B1 (en) Time linked scheduling of cell-based traffic
US5835494A (en) Multi-level rate scheduler
US7372857B1 (en) Methods and apparatus for scheduling tasks
KR20020022049A (en) Task scheduling and message passing
CN114205310A (en) A data transmission method, device and electronic device based on time-sensitive network
EP1638273B1 (en) Scheduling using quantum and deficit values
Bosman et al. Fixed-order scheduling on parallel machines
Manolache et al. Schedulability analysis of multiprocessor real-time applications with stochastic task execution times
Shirero et al. On the schedulability conditions on partial time slots
Yates et al. Updates with multiple service classes
US8612983B2 (en) Scheduling event streams depending on content information data
Baccelli et al. Extremal scheduling of parallel processing with and without real-time constraints
Hajek et al. Lex-optimal online multiclass scheduling with hard deadlines
Sarin et al. Equal processing time bicriteria scheduling on parallel machines
Chen et al. An approximate analysis of waiting time in multi-class M/G/1/./EDF queues
Nino-Mora Marginal productivity index policies for scheduling multiclass wireless transmissions
Jeon et al. Achievable loss probabilities and buffer allocation policies in ATM nodes with correlated arrivals
Saad-Bouzefrane et al. A performance analysis of distributed hard-real time applications
Xie et al. An efficient adaptive search algorithm for scheduling real-time traffic
Fendick et al. A heavy-traffic comparison of shared and segregated buffer schemes for queues with the head-of-line processor-sharing discipline
Goel et al. Scheduling data transfers in a network and the set scheduling problem