Related Experiment Video
Updated: Sep 7, 2025
10:09
Operation of the Collaborative Composite Manufacturing CCM System
Published on: October 1, 2019
6.7K
Pareto optimal algorithms for minimizing total (weighted) completion time and maximum cost on a single machine.
1College of Computer Science and Technology, Shandong Technology and Business University, Yantai 264005, China.
Mathematical Biosciences and Engineering : MBE
|June 22, 2022
Summary
This study presents efficient algorithms for the Pareto scheduling problem, aiming to minimize total weighted completion time and maximum cost on a single machine. The research focuses on specific scenarios where processing times, release dates, and weights are equal or arbitrary.
Area of Science:
- Operations Research
- Computer Science
- Algorithm Design
Background:
- The Pareto scheduling problem on a single machine is known to be strongly NP-hard.
- Minimizing total weighted completion time and maximum cost simultaneously presents significant computational challenges.
Purpose of the Study:
- To develop efficient algorithms for the Pareto scheduling problem.
- To address the NP-hard nature of the problem by providing polynomial-time solutions for specific cases.
Main Methods:
- The study employs algorithmic approaches to solve the Pareto scheduling problem.
- Focus is placed on developing algorithms with a running time complexity of O(n^3).
Main Results:
- Algorithms are presented for three distinct cases of the Pareto scheduling problem.
- These cases involve variations in processing times, release dates, and weights, including arbitrary and equal parameters.
Conclusions:
- The research provides effective $O(n^3)$ algorithms for specific instances of the strongly NP-hard Pareto scheduling problem.
- These findings contribute to the efficient solution of complex scheduling problems in operations research and computer science.
Related Concept Videos
01:22Machines: Problem Solving I
406
A toggle clamp is a mechanical device commonly used for holding and clamping objects in various applications, such as woodworking, metalworking, and assembly operations. Consider a toggle clamp subjected to a force of 200 N at the handle. The vertical clamping force can be calculated, provided the dimensions of the toggle clamp are known.
The toggle clamp system is a machine structure consisting of movable, pin-connected multi-force members that form a stabilized system to transmit forces. The...
The toggle clamp system is a machine structure consisting of movable, pin-connected multi-force members that form a stabilized system to transmit forces. The...
406
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
100
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
100
01:30Machines: Problem Solving II
367
Machines are complex structures consisting of movable, pin-connected multi-force members that work together to transmit forces. Consider a lifting tong carrying a 100 kg load. It comprises movable sections DAF and CBG linked together with member AB.
367
01:21Distributed Loads: Problem Solving
722
Beams are structural elements commonly employed in engineering applications requiring different load-carrying capacities. The first step in analyzing a beam under a distributed load is to simplify the problem by dividing the load into smaller regions, which allows one to consider each region separately and calculate the magnitude of the equivalent resultant load acting on each portion of the beam. The magnitude of the equivalent resultant load for each region can be determined by calculating...
722
01:25Multimachine Stability
226
Multimachine stability analysis is crucial for understanding the dynamics and stability of power systems with multiple synchronous machines. The objective is to solve the swing equations for a network of M machines connected to an N-bus power system.
In analyzing the system, the nodal equations represent the relationship between bus voltages, machine voltages, and machine currents. The nodal equation is given by:
In analyzing the system, the nodal equations represent the relationship between bus voltages, machine voltages, and machine currents. The nodal equation is given by:
226
01:16Statically Indeterminate Problem Solving
487
Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...
487