Algorithms for scheduling a single machine to minimize the weighted number of late jobs
Article Abstract:
A single-machine scheduling problem to minimize the weighted number of late jobs is considered in which each job has a processing time, a due date and a weight. Relaxing the integrality constraints in a zero-one formulation of the problem gives an algorithm for solving the linear programming problem. A reduction algorithm that uses this linear programming lower bound eliminates jobs from the problem. A branch and bound algorithm that uses the linear programming lower bound is also proposed.
Publication Name: Management Science
Subject: Business, general
ISSN: 0025-1909
Year: 1988
User Contributions:
Comment about this article or add new information about this topic:
An improved successive linear programming algorithm
Article Abstract:
Like other successive linear programming (SLP) algorithms, the penalty SLP or PSLP can be used to efficiently (yet simply) solve nonlinear optimization problems, such as those associated with nonlinear refinery models. The PSLP algorithm, while requiring a large penalty value, is more robust than other SLP algorithms, and has been successfully used in refinery models of up to 1,000 rows.
Publication Name: Management Science
Subject: Business, general
ISSN: 0025-1909
Year: 1985
User Contributions:
Comment about this article or add new information about this topic:
A Lagrangean based branch and bound algorithm for single machine sequencing with precedence constraints to minimize total weighted completion time
Article Abstract:
A branch and bound algorithm, based on a serial application of Lagrangean multipliers, can be used to determine the minimum sum of weighted completion lines for a single machine sequencing problem. The algorithm can be used to solve such problems with up to 100 jobs.
Publication Name: Management Science
Subject: Business, general
ISSN: 0025-1909
Year: 1985
User Contributions:
Comment about this article or add new information about this topic:
- Abstracts: Merger puts spotlight on planning a succession. Who's minding the super funds? Index and destiny
- Abstracts: Come Christmas, business says thanks to those that matter most. Two cheers for rollback
- Abstracts: Wiggles say oui, si, hai to change. The Olympics' big winners
- Abstracts: The effects of stock index futures trading on stock index volatility: an analysis of the asymmetric response of volatility to news
- Abstracts: Network Programming Models for Production Scheduling in Multi- Stage, Multi-Item Capacitated Systems. Mathematical Programming Approaches to Capacity-Constrained MRP Systems: Review, Formulation and Problem Reduction