This article considers a single machine scheduling problem in which the processing time of a job is a linear increasing function of its starting time. The objective is to minimize the weighted number of tardy jobs. A ...
详细信息
This article considers a single machine scheduling problem in which the processing time of a job is a linear increasing function of its starting time. The objective is to minimize the weighted number of tardy jobs. A pseudo-polynomial dynamic programming algorithm and a fully polynomial-time approximation scheme are proposed.
In this paper we study the NP-hard problem of scheduling n deteriorating jobs on in identical parallel machines to minimize the makespan. Each job's processing time is a linear nondecreasing function of its start ...
详细信息
In this paper we study the NP-hard problem of scheduling n deteriorating jobs on in identical parallel machines to minimize the makespan. Each job's processing time is a linear nondecreasing function of its start time. We present a fully polynomial-time approximation scheme for the problem, thus establishing that the problem is NP-hard in the ordinary sense only. (c) 2007 Elsevier B.V. All rights reserved.
A two-stage openshop consists of a machine in the first stage and a machine in the second stage;a job processed on the two-stage openshop means it is processed non-preemptively by each of the two machines, in whicheve...
详细信息
A two-stage openshop consists of a machine in the first stage and a machine in the second stage;a job processed on the two-stage openshop means it is processed non-preemptively by each of the two machines, in whichever order. We consider the scheduling problem at the availability of multiple parallel identical two-stage openshops, with the goal to minimize the makespan. By uncovering the important role of the critical job in the optimal schedule on a two-stage openshop, we propose to sort the jobs in the novel critical-job order, and use this order to design a pseudo-polynomialtime dynamic programming exact algorithm to solve our scheduling problem with any fixed number of two-stage openshops. Afterwards, using the standard scaling technique, we develop the dynamic programming algorithm into a fully polynomial-time approximation scheme. These results improve previously proposed constant ratio approximation algorithms.
Given a set of squares and a strip with bounded width and infinite height, we consider a square strip packaging problem, which we call the square independent packing problem (SIPP), to minimize the strip height so tha...
详细信息
Given a set of squares and a strip with bounded width and infinite height, we consider a square strip packaging problem, which we call the square independent packing problem (SIPP), to minimize the strip height so that all the squares are packed into independent cells separated by horizontal and vertical partitions. For the SIPP, we first investigate efficient solution representations and propose a compact representation that reduces the search space from Omega(n!) to O(2n), with n the number of given squares, while guaranteeing that there exists a solution representation that corresponds to an optimal solution. Based on the solution representation, we show that the problem is NP-hard. To solve the SIPP, we propose a dynamic programming method that can be extended to a fully polynomial-time approximation scheme (FPTAS). We also propose three mathematical programming formulations based on different solution representations and confirm their performance through computational experiments with a mathematical programming solver. Finally, we discuss several extensions that are relevant to practical applications.
This paper focuses on job scheduling with step learning and job rejection. The step learning model aims to reduce the processing time for jobs starting after a specific learning date. Our objective is to minimize the ...
详细信息
This paper focuses on job scheduling with step learning and job rejection. The step learning model aims to reduce the processing time for jobs starting after a specific learning date. Our objective is to minimize the sum of the maximum completion time of accepted jobs and the total rejection penalty of rejected jobs. We examine special cases of processing times for both single-machine and parallel-machine scenarios. For the former, we design a pseudo-polynomialtime algorithm, a 2-approximation algorithm and a fully polynomial-time approximation scheme (FPTAS) based on data rounding. For the latter, we present a fully polynomial-time approximation scheme achieved by trimming the state space. Additionally, for the general case of the single-machine problem, we propose a pseudo-polynomialtime algorithm.
This paper studies a single-machine due date assignment and scheduling problem in a disruptive environment, where a machine disruption may occur at a particular time that will last for a period of time with a certain ...
详细信息
This paper studies a single-machine due date assignment and scheduling problem in a disruptive environment, where a machine disruption may occur at a particular time that will last for a period of time with a certain probability, and the job due dates are determined by the decision-maker using the popular common due date assignment method. The goal is to determine jointly the optimal job sequence and the common due date so as to minimise the expected value of an integrated cost function that includes the earliness, tardiness and due date assignment costs. We analyse the computational complexity status of various cases of the problem, and develop pseudo-polynomial-time solution algorithms, randomised adaptive search algorithms, and fully polynomial-time approximation schemes for them, if viable. Finally, we conduct extensive numerical testing to assess the performance of the proposed algorithms.
In this paper, we consider the unbounded parallel batch machine scheduling with release dates and rejection. A job is either rejected with a certain penalty having to be paid, or accepted and processed in batches on t...
详细信息
In this paper, we consider the unbounded parallel batch machine scheduling with release dates and rejection. A job is either rejected with a certain penalty having to be paid, or accepted and processed in batches on the parallel batch machine. The processing time of a batch is defined as the longest processing time of the jobs contained in it. 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 this problem is binary NP-hard and provide a pseudo-polynomial-time algorithm. When the jobs have the same rejection penalty, the problem can be solved in polynomialtime. Finally, a 2-approximation algorithm and a fully polynomial-time approximation scheme are given for the problem. (C) 2008 Published by Elsevier B.V.
Given an undirected and edge-weighted graph G together with a set of ordered vertex-pairs, called st-pairs, we consider two problems of finding an orientation of all edges in G: min-sum orientation is to minimize the ...
详细信息
Given an undirected and edge-weighted graph G together with a set of ordered vertex-pairs, called st-pairs, we consider two problems of finding an orientation of all edges in G: min-sum orientation is to minimize the sum of the shortest directed distances between all st-pairs;and min-max orientation is to minimize the maximum shortest directed distance among all st-pairs. Note that these shortest directed paths for st-pairs are not necessarily edge-disjoint. In this paper, we first show that both problems are strongly NP-hard for planar graphs even if all edge-weights are identical, and that both problems can be solved in polynomialtime for cycles. We then consider the problems restricted to cacti, which form a graph class that contains trees and cycles but is a subclass of planar graphs. Then, min-sum orientation is solvable in polynomialtime, whereas min-max orientation remains NP-hard even for two st-pairs. However, based on LP-relaxation, we present a polynomial-time 2-approximation algorithm for min-max orientation. Finally, we give a fully polynomial-time approximation scheme (FPTAS) for min-max orientation on cacti if the number of st-pairs is a fixed constant.
Given a graph, the Hamiltonian path completion problem is to find an augmenting edge set such that the augmented graph has a Hamiltonian path. In this paper, we show that the Hamiltonian path completion problem will u...
详细信息
Given a graph, the Hamiltonian path completion problem is to find an augmenting edge set such that the augmented graph has a Hamiltonian path. In this paper, we show that the Hamiltonian path completion problem will unlikely have any constant ratio approximation algorithm unless NP = P. This problem remains hard to approximate even when the given subgraph is a tree. Moreover, if the edge weights are restricted to be either 1 or 2, the Hamiltonian path completion problem on a tree is still NP-hard. Then it is observed that this problem is strongly NP-hard, so it does not have any fully polynomial-time approximation scheme (FPTAS) unless NP = P. When the given tree is a k-tree, we give an approximation algorithm with performance ratio 1.5. (c) 2005 Elsevier B.V. All rights reserved.
We consider price optimization under the finite-mixture logit model. This model assumes that customers belong to one of a number of customer segments, where each customer segment chooses according to a multinomial log...
详细信息
We consider price optimization under the finite-mixture logit model. This model assumes that customers belong to one of a number of customer segments, where each customer segment chooses according to a multinomial logit model with segment-specific parameters. We reformulate the corresponding price optimization problem and develop a novel characterization. Leveraging this new characterization, we construct an algorithm that obtains prices at which the revenue is guaranteed to be at least (1- epsilon) times the maximum attainable revenue for any prespecified epsilon > 0. Existing global optimization methods require exponential time in the number of products to obtain such a result, which practically means that the prices of only a handful of products can be optimized. The running time of our algorithm, however, is exponential in the number of customer segments and only polynomial in the number of products. This is of great practical value, because in applications, the number of products can be very large, whereas it has been found in various contexts that a low number of segments is sufficient to capture customer heterogeneity appropriately. The results of our numerical study show that (i) ignoring customer segmentation can be detrimental for the obtained revenue, (ii) heuristics for optimization can get stuck in local optima, and (iii) our algorithm runs fast on a broad range of problem instances.
暂无评论