Counting and enumeration complexity with application to multicriteria scheduling

In this paper we tackle an important point of combinatorial optimisation: that of complexity theory when dealing with the counting or enumeration of optimal solutions. Complexity theory has been initially designed for decision problems and evolved over the years, for instance, to tackle particular features in optimisation problems. It has also evolved, more or less recently, towards the complexity of counting and enumeration problems and several complexity classes, which we review in this paper, have emerged in the literature. This kind of problems makes sense, notably, in the case of multicriteria optimisation where the aim is often to enumerate the set of the so-called Pareto optima. In the second part of this paper we review the complexity of multicriteria scheduling problems in the light of the previous complexity results. This paper appeared in 4OR 3(1), 1–21, 2005.     

A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems

Most classical scheduling research assumes that the objectives sought are common to all jobs to be scheduled. However, many real-life applications can be modeled by considering different sets of jobs, each one with its own objective(s), and an increasing number of papers addressing these problems has appeared over the last few years. Since so far the area lacks a unified view, the studied problems have received different names (such as interfering jobs, multi-agent scheduling, and mixed-criteria), some authors do not seem to be aware of important contributions in related problems, and solution procedures are often developed without taking into account existing ones. Therefore, the topic is in need of a common framework that allows for a systematic recollection of existing contributions, as well as a clear definition of the main research avenues. In this paper we review multicriteria scheduling problems involving two or more sets of jobs and propose an unified framework providing a common definition, name and notation for these problems. Moreover, we systematically review and classify the existing contributions in terms of the complexity of the problems and the proposed solution procedures, discuss the main advances, and point out future research lines in the topic.     

Paréto equilibria in multicriteria metagames

Summary In this paper we study the existence of Paréto equilibria of a multicriteria metagame. A theorem on existence of a Paréto equilibrium and a theorem on existence of a Nash equilibrium with weights are presented, which improve and extend some known results in the theory of games with multiple payoffs. Also relations between a Paréto equilibrium and other solution concepts of an optimization problem with multiple criteria are discussed. Partially supported by NSFC, NSFIMTF and MADIS. The authors are grateful to the referee's valuable comments and suggestions.     

Computational complexity of some scheduling problems with multiprocessor tasks

The paper is concerned with scheduling problems with multiprocessor tasks and presents conditions under which such problems can be solved in polynomial time. The application of these conditions is illustrated by two quite general scheduling problems. These results are complemented by a proof of NP-hardness of the problem with a UET task system, two parallel processors, the criterion of total completion time, and precedence constraints in the form of out-trees.     

Decision making in a fuzzy environment and its application to multicriteria power engineering problems

This paper presents results of research into the use of the Bellman–Zadeh approach to decision making in a fuzzy environment for solving multicriteria optimization problems. Its application conforms to the principle of guaranteed result and provides constructive lines in obtaining harmonious solutions on the basis of analyzing associated maxmin problems. The use of the Bellman–Zadeh approach has served as a basis for solving a problem of multicriteria allocation of resources (or their shortages) and developing a corresponding adaptive interactive decision making system (AIDMS1). AIDMS1 includes procedures for considering linguistic variables to reflect conditions that are difficult to formalize as well as procedures for constructing and correcting vectors of importance factors for goals. The use of these procedures permits one to realize an adaptive approach to processing information of a decision maker to provide successive improvment in solution quality. The results of the paper are universally applicable and are already being used to solve power engineering problems. It is illustrated by considering problems of multicriteria power and energy shortage allocation and multicriteria power system operation.     

工件可拒绝排序问题综述

可拒绝排序问题是兴起于2000年前后的有代表性、应用背景极强的的排序问题,是经典排序问题的衍生和推广.经典排序问题总是要求每个工件必须被加工,然而在实际中由于某些特殊原因,决策者会选择拒绝加工某些工件.把允许工件被拒绝的这类问题称为工件可拒绝排序问题,有的文献称之为外包的排序问题.这些问题不仅具有很强的应用价值,在理论上也有重要的意义.近年来该领域受到越来越广泛的关注,新的研究成果不断涌现.现就离线、在线情况下的可拒绝排序问题的进展情况作了全面介绍,展示了已有的研究成果和新的问题,给出了此方面的比较重要的参考文献,旨在帮助感兴趣的读者迅速了解问题研究的进展并由此进入此研究领域的前沿.     

Time complexity of single machine scheduling with stochastic precedence constraints

This paper deals with single machine scheduling problems with stochastic precedence relations (so calledGERT networks). Until now most investigations on such problems, dealt with algorithms running in polynomial time. On the other hand, for scheduling problems with deterministic precedence relations exist a lot of results about time complexity. Therefore, the object of this paper is to consider time complexity of scheduling problems with stochastic precedence constraints and to describe the boundary between theNP-hard problems and those which can be solved in polynomial time.     

On the complexity of project scheduling to minimize exposed time

We consider project scheduling where the project manager’s objective is to minimize the time from when an adversary discovers the project until the completion of the project. We analyze the complexity of the problem identifying both polynomially solvable and NP-hard versions of the problem. The complexity of the problem is seen to be dependent on the nature of renewable resource constraints, precedence constraints, and the ability to crash activities in the project.     

Multi-period lot-sizing with supplier selection: Structural results,complexity and algorithms

We consider a multi-period lot-sizing problem with multiple products and multiple suppliers. Demand is deterministic and time-varying. The objective is to determine order quantities to minimize the total cost over a finite planning horizon. This problem is strongly NP-hard. For a special case, we extend the classical zero-inventory-ordering principle and solve it by dynamic programming. Based on this new extension, we also develop a heuristic algorithm for the general problem and computationally show that it works well.     

A historical note on the complexity of scheduling problems

In 1972 E.M. Livshits and V.I. Rublinetsky published a paper in Russian, in which they presented linear-time reductions of the partition problem to a number of scheduling problems. Unaware of complexity theory, they argued that, since partition is not known to have a simple algorithm, one cannot expect to find simple algorithms for these scheduling problems either. Their work did not go completely unnoticed, but it received little recognition. We describe the approach and review the results.     

On minimax and Pareto optimal security payoffs in multicriteria games

In this paper, we characterize minimax and Pareto-optimal security payoff vectors for general multicriteria zero-sum matrix games, using properties similar to the ones that have been used in the single criterion case. Our results show that these two solution concepts are rather similar, since they can be characterized with nearly the same sets of properties. Their main difference is the form of consistency that each solution concept satisfies. We also prove that both solution concepts can transform into each other, in their corresponding domains.     

An extension of set partitioning with application to scheduling problems

The well known problems of set covering, set partitioning and set packing are defined and their interrelationship is considered. A natural generalisation called the extended set partitioning model is presented and the three standard models are shown to be special cases of this generalisation. In addition, the extended model includes another type of set problem which can be of greater use in certain applications. The model forms the basis of a computer assisted bus crew scheduling system developed by the authors. The system is in regular use by Dublin City Services in the Republic of Ireland. Finally, the equivalence between a special case of the set partitioning problem and the shortest route problem is considered and it is shown that this equivalence also applies to the extended model.     

The counting complexity of a simple scheduling problem

Let T be a set of tasks. Each task has a non-negative processing time and a deadline. The problem of determining whether or not there is a schedule of the tasks in T such that a single machine can finish processing each of them before its deadline is polynomially solvable. We prove that counting the number of schedules satisfying this condition is #P-complete.     

有关单机两代理排序问题的两个结果

研究了两个单机两代理排序问题. 在第一个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化最大工件费用. 在第二个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化所有工件的最大完工时间. 证明了第一个问题是强NP-难的, 改进了已有的一般意义NP-难的结果; 对第二个问题给出了一个与现有的动态规划算法不同的动态规划算法.     

ARMMS: Analogical reasoning model management system for multicriteria vehicle scheduling

The transportation industry problem of scheduling vehicles combines the spatial characteristics of routing with time domain considerations of activity schedules. The problem is complex because of the numerous interacting constraints in the spatial and time domains. Further, some of the constraints are flexible and some arise in real-time. The scheduling problem is often presented with multiple objectives that are not all economic in nature and which can be contradictory to one another. In response to these needs, this paper describes an analogical reasoning model management system, called ARMMS, designed in the domain of vehicle scheduling. ARMMS consists of knowledge bases and data bases, a truth maintenance system, a user interface, an inference engine, a learning mechanism, and a model library. Given a scheduling problem, ARMMS searches its memory for solutions. If no solution is available, ARMMS falls back on an analogical problem solving approach in which similar experience can be recalled, and solutions to new, but similar, problems can be constructed. If no similar experience exists, ARMMS intelligently selects an appropriate algorithmic model from its model library, based on the input parameters and problem type, to solve the given problem. By combining experts' knowledge, analogical problem-solving approaches, and algorithmic methods, ARMMS provides an efficient problem-solving approach for vehicle scheduling and routing. ARMMS is also a feasible base for the development of intelligent model management systems.     

Reducibility among single machine weighted completion time scheduling problems

Various sum of weighted completion time problems are compared. The constraints considered include release date, deadline, and continuous machine processing. Relations between the problems are developed by examining the computational complexity of transforming one problem class into another. These results give indications of the relative computational effort required to solve different problem classes.     

Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan

We consider a scheduling problem in which n jobs are to be processed on a single machine. The jobs are processed in batches and the processing time of each job is a simple linear function of its waiting time, i.e., the time between the start of the processing of the batch to which the job belongs and the start of the processing of the job. The objective is to minimize the makespan, i.e., the completion time of the last job. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is B  , the problem remains strongly NP-hard when B?U$B?U$ for a variable U?2$U?2$ or B?U$B?U$ for any constant U?2$U?2$. For the case of B?U$B?U$, we present a dynamic programming algorithm that runs in pseudo-polynomial time and a fully polynomial time approximation scheme (FPTAS) for any constant U?2$U?2$. Furthermore, we provide an optimal linear time algorithm for the special case where the jobs are subject to a linear precedence constraint, which subsumes the case where all the job growth rates are equal.     

The Holonomic Ansatz I. Foundations and Applications to Lattice Path Counting

Many combinatorial quantities belong to the holonomic ansatz. For example, sequences enumerating lattice paths. Once this fact is known, many times empirically obtained “conjectures” can be easily proved automatically. Accompanied by Maple packages GuessHolo2 and GuessHolo3 available from Zeilberger’s website. Supported in part by the NSF. . Received October 19, 2006