Scheduling subject to resource constraints: classification and complexity

In deterministic sequencing and scheduling problems, jobs are to be processed on machines of limited capacity. We consider an extension of this class of problems, in which the jobs require the use of additional scarce resources during their execution. A classification scheme for resource constraints is proposed and the computational complexity of the extended problem class is investigated in terms of this classification. Models involving parallel machines, unit-time jobs and the maximum completion time criterion are studied in detail; other models are briefly discussed.     

Branch and bound based solution algorithms for the budget constrained discrete time/cost trade-off problem

The time/cost trade-off models in project management aim to reduce the project completion time by putting extra resources on activity durations. The budget problem in discrete time/cost trade-off scheduling selects a time/cost mode for each activity so as to minimize the project completion time without exceeding the available budget. There may be alternative modes that solve the budget problem optimally and each solution may have a different total cost value. In this study we consider the budget problem and aim to find the minimum cost solution among the minimum project completion time solutions. We analyse the structure of the problem together with its linear programming relaxation and derive some mechanisms for reducing the problem size. We solve the reduced problem by branch and bound based optimization and heuristic algorithms. We find that our branch and bound algorithm finds optimal solutions for medium-sized problem instances in reasonable times and the heuristic algorithms produce high quality solutions very quickly.     

Parallel-machine scheduling with non-simultaneous machine available time

We consider a problem of scheduling n independent jobs on m parallel identical machines. The jobs are available at time zero, but the machines may not be available simultaneously at time zero. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time and total absolute differences in completion times; minimizing a cost function containing total waiting time and total absolute differences in waiting times. In this paper, we present polynomial time algorithm to solve this problem.     

Going Off the Grid: Iterative Model Selection for Biclustered Matrix Completion

We consider the problem of performing matrix completion with side information on row-by-row and column-by-column similarities. We build upon recent proposals for matrix estimation with smoothness constraints with respect to row and column graphs. We present a novel iterative procedure for directly minimizing an information criterion to select an appropriate amount of row and column smoothing, namely, to perform model selection. We also discuss how to exploit the special structure of the problem to scale up the estimation and model selection procedure via the Hutchinson estimator, combined with a stochastic Quasi-Newton approach. Supplementary material for this article is available online.     

Scheduling deteriorating jobs subject to job or machine availability constraints

We consider two problems of scheduling a set of independent, non-preemptable and proportionally deteriorating jobs on a single machine. In the first problem, the machine is not continuously available for processing but the number of non-availability periods, the start time and end time of each period are known in advance. In the second problem, the machine is available all the time but for each job a ready time and a deadline are defined. In both problems the criterion of schedule optimality is the maximum completion time. We show that the decision version of the first (the second) problem is NP-complete in the ordinary or in the strong sense, depending on the number of non-availability periods (the number of ready times and deadlines).     

V-shape property for job sequences that minimize the expected completion time variance

We consider the problem of sequencing n jobs with random processing time on a single machine so as to minimize the expected variance of job completion times. Our main result is a new sufficient condition for an optimal sequence to be V-shaped in terms of the mean processing times when n ⩾ 3. We show that this condition is satisfied by a wide variety of problem instances, including those in which the processing times follow different patterns of distributions. This result relaxes a condition proposed before.     

Product line optimization in the presence of preferences for compromise alternatives

Recent advances in customer choice analysis demonstrated the strong impact of compromise alternatives on the behaviour of decision-makers in a wide range of decision situations. Compromise alternatives are characterized by an intermediate performance on some of the relevant attributes. For instance, price compromises are well known in the sense that customers tend to buy neither the cheapest, nor the most expensive alternative, but the mid-priced one. However, thus far, the literature on product line optimization has not considered such context effects.In this paper, we propose a model-based approach for optimal product line selection which incorporates customers’ preferences for compromise alternatives. We consider customer choice in a realistic, sophisticated fashion by applying an established utility model that integrates compromise variables into a multinomial logit model. We formulate the resulting optimization problem as a mixed-integer linear program. The challenging feature for modelling – making the formulation substantially more complicated than existing ones without compromises – are the endogenous effects of selected products on other alternatives’ utilities that need to be adequately captured via compromise variables. Based on data we collected by a stated choice experiment in a retail setting, we perform a computational study and demonstrate the superiority of our product line selection approach compared to a reference model that does not take compromises into account. Even under uncertainty of the estimated utility parameters, profit gains of, on average, 23% can be achieved in our experimental setting.     

Job selection and sequencing on a single machine in a random environment

We examine a single machine scheduling problem with random processing times and deadline. Given a set of independent jobs having specified initiation costs and terminal revenues, the objective is to select a subset of the jobs and sequence the selected jobs such that the expected profit is maximized. The job selection aspect considered by us marks a clear departure from the pure sequencing focus found in the traditional scheduling literature. In this paper, we assume an exponentially distributed deadline and do not allow preemption. Even under these conditions, the selection and sequencing problem remains quite difficult (unlike its pure sequencing counterpart); we in fact conjecture that the problem is NP-hard. However, we show that the problem can be efficiently solved as long as the cost parameter is agreeable or an approximate solution is acceptable. To this end, we describe several solution properties, present dynamic programming algorithms (one of which exhibits a pseudo-polynomial time worst-case complexity), and propose a fully-polynomial time approximation scheme. In addition, we study a number of special cases which can be solved in polynomial time. Finally, we summarize our work and discuss an extension where the jobs are precedence related.     

Some aspects of intuitionistic fuzzy sets

We first discuss the significant role that duality plays in many aggregation operations involving intuitionistic fuzzy subsets. We then consider the extension to intuitionistic fuzzy subsets of a number of ideas from standard fuzzy subsets. In particular we look at the measure of specificity. We also look at the problem of alternative selection when decision criteria satisfaction is expressed using intuitionistic fuzzy subsets. We introduce a decision paradigm called the method of least commitment. We briefly look at the problem of defuzzification of intuitionistic fuzzy subsets.     

Autocovariance Function Estimation via Penalized Regression

The work revisits the autocovariance function estimation, a fundamental problem in statistical inference for time series. We convert the function estimation problem into constrained penalized regression with a generalized penalty that provides us with flexible and accurate estimation, and study the asymptotic properties of the proposed estimator. In case of a nonzero mean time series, we apply a penalized regression technique to a differenced time series, which does not require a separate detrending procedure. In penalized regression, selection of tuning parameters is critical and we propose four different data-driven criteria to determine them. A simulation study shows effectiveness of the tuning parameter selection and that the proposed approach is superior to three existing methods. We also briefly discuss the extension of the proposed approach to interval-valued time series. Supplementary materials for this article are available online.     

Parallel-Machine Scheduling Problems with Earliness and Tardiness Penalties

We consider the problem of assigning a common due-date and sequencing a set of simultaneously available jobs on several identical parallel-machines. The objective is to minimize some penalty function of earliness, tardiness and due-date values. We show that the problem is NP-hard with either a total or a maximal penalty function. For the problem with a total penalty function, we show that the special case in which all jobs have an equal processing time is polynomially-solvable.     

Two-machine flow-shop scheduling with equal processing time on the second machine for minimizing total weighted completion time

We consider the classical two-machine flow-shop scheduling for minimizing the total weighted completion time. For this problem, the computational complexity of a version in which the jobs have a common processing time on the second machine, has not been addressed. We show that the problem is unary NP-hard, answering an open problem posed in Zhu et al. (2016). Then we present an approximation algorithm for the problem with worst-case performance ratio at most 2.     

Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect

In this paper we consider the single machine scheduling problems with exponential sum-of-logarithm-processing-times based learning effect. By the exponential sum-of-logarithm-processing-times based learning effect, we mean that the processing time of a job is defined by an exponent function of the sum of the logarithm of the processing times of the jobs already processed. We consider the following objective functions: the makespan, the total completion time, the sum of the quadratic job completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.     

恶化率与工件无关的线性加工时间调度问题

讨论恶化率与工件无关的线性加工时间调度问题 .对于工件间具有平行链约束 ,目标函数为极小化最大完工时间的单机问题 ,分别就链不允许中断和链允许中断两种情况给出了最优算法 .对于工件间没有优先约束 ,目标函数为极小化完工时间和的平行机问题 ,证明了工件按基本加工时间不减排列可以得到最优调度 .     

Using multiple sources of information to recognize and classify objects

In this paper we consider the problem of selecting an object or a course of action from a set of possible alternatives. To give the paper focus, we concentrate initially on an object recognition problem in which the characteristic features of the object are reported by remote sensors. We then extend the method to a more general class of selection problems and consider several different scenarios.

Information is provided by a set of knowledge system reports on a single feature, and the output from these systems is not totally explicit but provides posible values for the observed feature along with a degree of certitude.We use fuzzy sets to represent this vague information. Information from independent sources is combined using the Dempster-Shafer approach adapted to the situation in which the focal elements are fuzzy as in the recent paper by J. Yen [7]. We base our selection rule on the belief and plausibility functions generated by this approach to accessing evidence.

For situations in which the information is too sparse and/or too vague to make a single selection, we construct a preference relationship based on the concept of averaged subsethood for fuzzy sets as discussed by B. Koskoin [4]. We also define an explicit metric upon which to base our selection mechanism for situations in which the Dempster-Shafer rule of combination is inappropriate     

A visual interactive approach for multiple criteria decision making with monotone utility functions

We consider the problem of choosing the best of a set of alternatives where each alternative is evaluated on multiple criteria. We develop a visual interactive approach assuming that the decision maker (DM) has a general monotone utility function. The approach partitions the criteria space into nonoverlapping cells. The DM uses various graphical aids to move between cells and to further manipulate selected cells with the goal of creating cells that have ideal points less preferred than an alternative. When the DM identifies such cells, all alternatives in those cells are eliminated from further consideration. The DM may also compare pairs of alternatives. The approach terminates with the most preferred alternative of the DM.     

Precedence constrained parallel-machine scheduling of position-dependent jobs

We consider parallel-machine job scheduling problems with precedence constraints. Job processing times are variable and depend on positions of jobs in a schedule. The objective is to minimize the maximum completion time or the total weighted completion time. We specify certain conditions under which the problem can be solved by scheduling algorithms applied earlier for fixed job processing times.     

A tight lower bound for the completion time variance problem

We consider the completion time variance problem. Our main result is a tight lower bound for the mean completion time of an optimal sequence. This result can be applied to reduce the time required to solve the problem.     

Single machine scheduling with a general exponential learning effect

In this paper we consider the scheduling problem with a general exponential learning effect and past-sequence-dependent (p-s-d) setup times. By the general exponential learning effect, we mean that the processing time of a job is defined by an exponent function of the total weighted normal processing time of the already processed jobs and its position in a sequence, where the weight is a position-dependent weight. The setup times are proportional to the length of the already processed jobs. We consider the following objective functions: the makespan, the total completion time, the sum of the δ ? 0th power of completion times, the total weighted completion time and the maximum lateness. We show that the makespan minimization problem, the total completion time minimization problem and the sum of the quadratic job completion times minimization problem can be solved by the smallest (normal) processing time first (SPT) rule, respectively. We also show that the total weighted completion time minimization problem and the maximum lateness minimization problem can be solved in polynomial time under certain conditions.