Single machine scheduling with release dates and rejection

In this paper, we consider the single machine scheduling problem with release dates and rejection. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on the machine. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. We show that the problem is NP-hard in the ordinary sense. Then we provide two pseudo-polynomial-time algorithms. Consequently, two special cases can be solved in polynomial-time. Finally, a 2-approximation algorithm and a fully polynomial-time approximation scheme are given for the problem.     

Theoretical convergence of large-step primal—dual interior point algorithms for linear programming

This paper proposes two sets of rules, Rule G and Rule P, for controlling step lengths in a generic primal—dual interior point method for solving the linear programming problem in standard form and its dual. Theoretically, Rule G ensures the global convergence, while Rule P, which is a special case of Rule G, ensures the O(nL) iteration polynomial-time computational complexity. Both rules depend only on the lengths of the steps from the current iterates in the primal and dual spaces to the respective boundaries of the primal and dual feasible regions. They rely neither on neighborhoods of the central trajectory nor on potential function. These rules allow large steps without performing any line search. Rule G is especially flexible enough for implementation in practically efficient primal—dual interior point algorithms.Part of the research was done when M. Kojima and S. Mizuno visited at the IBM Almaden Research Center. Partial support from the Office of Naval Research under Contracts N00014-87-C-0820 and N00014-91-C-0026 is acknowledged.     

Interior path following primal-dual algorithms. part I: Linear programming

We describe a primal-dual interior point algorithm for linear programming problems which requires a total of number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds the Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea.     

A class of polynomially solvable 0-1 programming problems and an application

It is well known that general 0-1 programming problems are NP-Complete and their optimal solutions cannot be found with polynomial-time algorithms unless P=NP. In this paper, we identify a specific class of 0-1 programming problems that is polynomially solvable, and propose two polynomial-time algorithms to find its optimal solutions. This class of 0-1 programming problems commits to a wide range of real-world industrial applications. We provide an instance of representative in the field of supply chain man...     

Integer knapsack problems with set-up weights

The Integer Knapsack Problem with Set-up Weights (IKPSW) is a generalization of the classical Integer Knapsack Problem (IKP), where each item type has a set-up weight that is added to the knapsack if any copies of the item type are in the knapsack solution. The k-item IKPSW (kIKPSW) is also considered, where a cardinality constraint imposes a value k on the total number of items in the knapsack solution. IKPSW and kIKPSW have applications in the area of aviation security. This paper provides dynamic programming algorithms for each problem that produce optimal solutions in pseudo-polynomial time. Moreover, four heuristics are presented that provide approximate solutions to IKPSW and kIKPSW. For each problem, a Greedy heuristic is presented that produces solutions within a factor of 1/2 of the optimal solution value, and a fully polynomial time approximation scheme (FPTAS) is presented that produces solutions within a factor of ε of the optimal solution value. The FPTAS for IKPSW has time and space requirements of O(nlog n+n/ε ²+1/ε ³) and O(1/ε ²), respectively, and the FPTAS for kIKPSW has time and space requirements of O(kn ²/ε ³) and O(k/ε ²), respectively.     

单机主次指标排序问题(英文)

本文研究了单机主次指标排序问题1|rj,pmtn|∑Uj|Tmax.在同工期且准备时间和工期具有一致性的情形下,给出了该问题的允许中断抢先的多项式时间算法.     

加工时间和工期一致的单机主次指标排序问题1｜｜∑U｜Tmax

本研究了单机主次指标排序问题1||∑U|Tmax。在加工时间和工期具有一致性的情形下，给出了该问题的多项式时间算法。     

New trajectory-following polynomial-time algorithm for linear programming problems

A new interior point method for the solution of the linear programming problem is presented. It is shown that the method admits a polynomial time bound. The method is based on the use of the trajectory of the problem, which makes it conceptually very simple. It has the advantage above related methods that it requires no problem transformation (either affine or projective) and that the feasible region may be unbounded. More importantly, the method generates at each stage solutions of both the primal and the dual problem. This implies that, contrary to the simplex method, the quality of the present solution is known at each stage. The paper also contains a practical (i.e., deepstep) version of the algorithm.The author is indebted to J. Bisschop, P. C. J. M. Geven, J. H. Van Lint, J. Ponstein, and J. P. Vial for their remarks on an earlier version of this paper.