We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Scheduling Algorithms for the Maximal Total Revenue on a Single Processor with Starting Time Penalty.
- Authors
Un Gi Joo
- Abstract
This paper considers a revenue maximization problem on a single processor. Each job is identified as its processing time, initial reward, reward decreasing rate, and preferred start time. If the processor starts a job at time zero, revenue of the job is its initial reward. However, the revenue decreases linearly with the reward decreasing rate according to its processing start time till its preferred start time and finally its revenue is zero if it is started the processing after the preferred time. Our objective is to find the optimal sequence which maximizes the total revenue. For the problem, we characterize the optimal solution properties and prove the NP-hardness. Based upon the characterization, we develop a branch-and-bound algorithm for the optimal sequence and suggest five heuristic algorithms for efficient solutions. The numerical tests show that the characterized properties are useful for effective and efficient algorithms.
- Subjects
REVENUE; NUMERICAL analysis; BRANCH &; bound algorithms; HEURISTIC algorithms; MATHEMATICAL models
- Publication
Management Science & Financial Engineering, 2012, Vol 18, Issue 1, p13
- ISSN
2287-2043
- Publication type
Article
- DOI
10.7737/MSFE.2012.18.1.013