Minimizing weighted mean absolute deviation of job completion times from their weighted mean

We address a single-machine scheduling problem where the objective is to minimize the weighted mean absolute deviation of job completion times from their weighted mean. This problem and its precursors aim to achieve the maximum admissible level of service equity. It has been shown earlier that the unweighted version of this problem is NP-hard in the ordinary sense. For that version, a pseudo-polynomial time dynamic program and a 2-approximate algorithm are available. However, not much (except for an important solution property) exists for the weighted version. In this paper, we establish the relationship between the optimal solution to the weighted problem and a related one in which the deviations are measured from the weighted median (rather than the mean) of the job completion times; this generalizes the 2-approximation result mentioned above. We proceed to give a pseudo-polynomial time dynamic program, establishing the ordinary NP-hardness of the problem in general. We then present a fully-polynomial time approximation scheme as well. Finally, we report the findings from a limited computational study on the heuristic solution of the general problem. Our results specialize easily to the unweighted case; they also lead to an approximation of the set of schedules that are efficient with respect to both the weighted mean absolute deviation and the weighted mean completion time.     

Batch scheduling and common due date assignment problem: An NP-hard case

An important special case of the problem studied in Cheng and Kovalyov (1996) arises when there are equal set-up times and equal job processing times. Computational complexity of this case was indicated to be open, however. I prove its NP-hardness.     

On A Scheduling Problem of Time Deteriorating Jobs

We consider a scheduling problem with a single machine and a set of jobs which have to be processed sequentially. While waiting for processing, jobs may deteriorate, causing the processing requirement of each job to grow after a fixed waiting timet₀. We prove that the problem of minimizing the makespan—completion time for all jobs—is NP-hard. Next we consider the problem for a natural special case where the job requirement grows linearly at a job-specific rate aftert₀. We develop a fully polynomial time approximation scheme for the problem in this case. We also give further NP-hardness results, and a polynomial time algorithm for the case where the job-specific rate is proportional to the initial processing requirement of each job.     

三机流水作业问题若干特殊情形的NP困难性

本文研究以加工总为目标函数的三台机器流水作业问题的特殊情形的计算复杂性,证明了下列情形为ＮＰ困难的：所有工作在第二台机器上有相同的加工时间;所有工作在第一和第三台机器上有相册的加工时间;每个工件至少有一个零工序;每个工件有一个丢失的工序。     

Scheduling jobs with position-dependent processing times

The paper is devoted to some single machine scheduling problems, where job processing times are defined by functions dependent on their positions in the sequence. It is assumed that each job is available for processing at its ready time. We prove some properties of the special cases of the problems for the following optimization criteria: makespan, total completion time and total weighted completion time. We prove strong NP-hardness of the makespan minimization problem for two different models of job processing time. The reductions are done from the well-known 3-Partition Problem. In order to solve the makespan minimization problems, we suggest the Earliest Ready Date algorithms, for which the worst-case ratios are calculated. We also prove that the makespan minimization problem with job ready times is equivalent to the maximum lateness minimization problem.     

Parallel machine scheduling problems with a single server

In this paper, we consider the problem of scheduling jobs on parallel machines with setup times. The setup has to be performed by a single server. The objective is to minimize the schedule length (makespan), as well as the forced idle time. The makespan problem is known to be NP-hard even for the case of two identical parallel machines. This paper presents a pseudopolynomial algorithm for the case of two machines when all setup times are equal to one. We also show that the more general problem with an arbitrary number of machines is unary NP-hard and analyze some list scheduling heuristics for this problem. The problem of minimizing the forced idle time is known to be unary NP-hard for the case of two machines and arbitrary setup and processing times. We prove unary NP-hardness of this problem even for the case of constant setup times. Moreover, some polynomially solvable cases are given.     

“Product Partition” and related problems of scheduling and systems reliability: Computational complexity and approximation

Problem Product Partition differs from the NP-complete problem Partition in that the addition operation is replaced by the multiplication operation. Furthermore it differs from the NP-complete problem Subset Product in that it does not contain the product value B in its input. We prove that problem Product Partition and several of its modifications are NP-complete in the strong sense. Our results imply the strong NP-hardness of a number of scheduling problems with start-time-dependent job processing times and a problem of designing a reliable system with a series–parallel structure. It should be noticed that the strong NP-hardness of the considered optimization problems does not preclude the existence of a fully polynomial time approximation scheme (FPTAS) for them. We present a simple FPTAS for one of these problems.     

Scheduling with step-improving processing times

We consider the scheduling problem of minimizing the makespan on a single machine with step-improving job processing times around a common critical date. For this problem we give an NP-hardness proof, a fast pseudo-polynomial time algorithm, an FPTAS, and an on-line algorithm with best possible competitive ratio.     

NP-complete problems for systems of Linear polynomial’s values divisibilities

The paper studies the algorithmic complexity of subproblems for satisfiability in positive integers of simultaneous divisibility of linear polynomials with nonnegative coefficients. In the general case, it is not known whether this problem is in the class NP, but that it is in NEXPTIME is known. The NP-completeness of two series of restricted versions of this problem such that a divisor of a linear polynomial is a number in the first case, and a linear polynomial is a divisor of a number in the second case is proved in the paper. The parameters providing the NP-completeness of these problems have been established. Their membership in the class P has been proven for smaller values of these parameters. For the general problem SIMULTANEOUS DIVISIBILITY OF LINEAR POLYNOMIALS, NP-hardness has been proven for its particular case, when the coefficients of the polynomials are only from the set {1, 2} and constant terms are only from the set {1, 5}.     

The strong NP-hardness of the maximum lateness minimization scheduling problem with the processing-time based aging effect

In this paper, we analyse the single machine maximum lateness minimization scheduling problem with the processing time based aging effect, where the processing time of each job is described by a non-decreasing function dependent on the sum of the normal processing times of preceded jobs. The computational complexity of this problem was not determined. However, we show it is strongly NP-hard by proving the strong NP-hardness of the single machine maximum completion time minimization problem with this aging model and job deadlines. Furthermore, we determine the boundary between polynomially solvable and NP-hard cases.     

Two-Machine Flowshop Batching and Scheduling

We consider in this paper a two-machine flowshop scheduling problem in which the first machine processes jobs individually while the second machine processes jobs in batches. The forming of each batch on the second machine incurs a constant setup time. The objective is to minimize the makespan. This problem was previously shown to be NP-hard in the ordinary sense. In this paper, we first present a strong NP-hardness result of the problem. We also identify a polynomially solvable case with either anticipatory or non-anticipatory setups. We then establish a property that an optimal solution for the special case is a lower bound for the general problem. To obtain near-optimal solutions for the general problem, we devise some heuristics. The lower bound is used to evaluate the quality of the heuristic solutions. Results of computational experiments reveal that the heuristics produce solutions with small error ratios. They also suggest that the lower bound is close to the optimal solution.     

一个不同时刻加工成本有差异的单机排序问题

考虑一个单机排序问题:一批工件在零时刻到达可加工,加工时不可中断,在某个给定时间区间外的加工工时将招致额外的加工成本;当时间区间为给定参数时,要求确定一个最优加工序,当时间区间为决策变量时,要求找到一个最优序及最优区间位置, 由此来最小化总额外加工成本．文中对各种区间外单位加工工时之额外成本的情况给出了多项式算法, NP-hardness的证明及伪多项式时间算法．     

Fabrication scheduling on a single machine with due date constraints

There is a fabrication machine available for processing a set of jobs. Each job is associated with a due date and consists of two parts, one is common among all products and the other is unique to itself. The unique components are processed individually and the common parts are grouped into batches for processing. A constant setup time is incurred when each batch is formed. The completion time of a job is defined as the time when both of its unique and common components are completed. In this paper, we consider two different objectives. The first problem seeks to minimize the maximum tardiness, and the second problem is to minimize the number of tardy jobs. To minimize the maximum tardiness, we propose a dynamic programming algorithm that optimally solves the problem in polynomial time. Next, we show NP-hardness proof and design a pseudo-polynomial time dynamic programming algorithm for the problem of minimizing the number of tardy jobs.     

A note on proving the strong NP-hardness of a scheduling problem with position dependent job processing times

In this paper, we show that the strong NP-hardness proof of the single machine makespan minimization problem with ready times and job processing times described by a non-increasing power function dependent on a job position in a sequence presented in Bachman and Janiak (J Oper Res Soc 55:257–264, 2004) is incorrect. Namely, the applied transformation from 3- Partition problem to the considered scheduling problem is polynomial not pseudopolynomial. Thus, the related problem is NP-hard, but it is not proved to be strongly NP-hard.     

How to determine basis stability in interval linear programming

Interval linear programming (ILP) was introduced in order to deal with linear programming problems with uncertainties that are modelled by ranges of admissible values. Basic tasks in ILP such as calculating the optimal value bounds or set of all possible solutions may be computationally very expensive. However, if some basis stability criterion holds true then the problems becomes much more easy to solve. In this paper, we propose a method for testing basis stability. Even though the method is exponential in the worst case (not surprisingly due to NP-hardness of the problem), it is fast in many cases.     

Rescheduling with new orders and general maximum allowable time disruptions

We study the rescheduling with new orders on a single machine under the general maximum allowable time disruptions. Under the restriction of general maximum allowable time disruptions, each original job has an upper bound for its time disruption (regarded as the maximum allowable time disruption of the job), or equivalently, in every feasible schedule, the difference of the completion time of each original job compared to that in the pre-schedule does not exceed its maximum allowable time disruption. We also consider a stronger restriction which additionally requires that, in a feasible schedule, the starting time of each original job is not allowed to be scheduled smaller than that in the pre-schedule. Scheduling objectives to be minimized are the maximum lateness and the total completion time, respectively, and the pre-schedules of original jobs are given by EDD-schedule and SPT-schedule, respectively. Then we have four problems for consideration. For the two problems for minimizing the maximum lateness, we present strong NP-hardness proof, provide a simple 2-approximation polynomial-time algorithm, and show that, unless \(\text {P}= \text {NP}\), the two problems cannot have an approximation polynomial-time algorithm with a performance ratio less than 2. For the two problems for minimizing the total completion time, we present strong NP-hardness proof, provide a simple heuristic algorithm, and show that, unless \(\text {P}= \text {NP}\), the two problems cannot have an approximation polynomial-time algorithm with a performance ratio less than 4/3. Moreover, by relaxing the maximum allowable time disruptions of the original jobs, we present a super-optimal dual-approximation polynomial-time algorithm. As a consequence, if the maximum allowable time disruption of each original job is at least its processing time, then the two problems for minimizing the total completion time are solvable in polynomial time. Finally, we show that, under the agreeability assumption (i.e., the nondecreasing order of the maximum allowable time disruptions of the original jobs coincides with their scheduling order in the pre-schedule), the four problems in consideration are solvable in polynomial time.     

有负荷约束的指派问题

通过组合最优化的理论和方法,研究机器有负荷(时间)限制的指派问题,证明其NP困难性,并建立多项式可解的特殊情形算法及一般情形的隐枚举算法.     

Scheduling on a Batch Processing Machine with Split Compatibility Graphs

We consider the problem of minimizing the makespan on a batch processing machine, in which jobs are not all compatible. Only compatible jobs can be included into the same batch. This relation of compatibility is represented by a split graph. All jobs are available at the same date. The capacity of the batch processing machine is finite or infinite. The processing time of a batch is given by the processing time of the longest job in the batch. We establish the NP-hardness of the general problem and present polynomial algorithms for several special cases.     

Customer order scheduling to minimize the number of late jobs

In the order scheduling problem, every job (order) consists of several tasks (product items), each of which will be processed on a dedicated machine. The completion time of a job is defined as the time at which all its tasks are finished. Minimizing the number of late jobs was known to be strongly NP-hard. In this note, we show that no FPTAS exists for the two-machine, common due date case, unless P = NP. We design a heuristic algorithm and analyze its performance ratio for the unweighted case. An LP-based approximation algorithm is presented for the general multicover problem. The algorithm can be applied to the weighted version of the order scheduling problem with a common due date.     

Location problems

Recent developments for several location problems are surveyed. These include: graph theoretic and combinatorial formulations of the simple plant location problem, the NP-hardness of some p-center problems, worst-case bounds for several polynomial-time heuristics for some p-center problems, and a general solution to a class of one facility network problems with convex cost functions.