Multi-agent scheduling on a single machine with max-form criteria

We consider multi-agent scheduling on a single machine, where the objective functions of the agents are of the max-form. For the feasibility model, we show that the problem can be solved in polynomial time even when the jobs are subject to precedence restrictions. For the minimality model, we show that the problem is strongly NP-hard in general, but can be solved in pseudo-polynomial-time when the number of agents is a given constant. We then identify some special cases of the minimality model that can be solved in polynomial-time.     

Power-aware scheduling of preemptable jobs on identical parallel processors to meet deadlines

This paper deals with a power-aware scheduling of preemptable independent jobs on identical parallel processors where ready time for each job is given and its completion time has to meet a given deadline. Jobs are described by (different) continuous, strictly concave functions relating their processing speeds at a time to the amount of power allotted at the moment. Power is a continuous, doubly constrained resource, i.e. both: its availability at each time instant and consumption over scheduling horizon are constrained. A methodology based on properties of minimum-length schedules is utilized to determine the existence of a feasible schedule for given amounts of energy and power. The question about minimum levels of power and energy ensuring the existence of a feasible schedule for a given set of jobs is also studied.     

众数计算的进一步讨论

在众数计算应该具备的两个假设和两个性质的条件下,常用的众数计算公式得到的结果只考虑了众数组及其前后两组,因此具有一定的局限性。一种考虑全部组频次的众数计算公式可以得到考虑更为全面的结果,并且这种计算公式也具有原公式所具有的一切良好属性。结合实例可以发现改进后的众数计算公式可以得到更佳的结果。     

关于高校图书馆典藏岗位设置的思考

本文探讨了传统典藏管理岗位设置的不合理性、新典藏管理方式与传统典藏管理方式相比较显示出的优越性及应注意的问题。     

用Excel软件实现最大似然估计数值计算的方法

本文给出用Excel软件实现最大似然估计数值计算求解的方法。内容包括对似然方程求数值解、直接对似然函数或对数似然函数求极大值以及分组数据最大似然估计的数值计算。     

Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan

This paper studies the single-machine scheduling problem with deteriorating jobs and learning considerations. The objective is to minimize the makespan. We first show that the schedule produced by the largest growth rate rule is unbounded for our model, although it is an optimal solution for the scheduling problem with deteriorating jobs and no learning. We then consider three special cases of the problem, each corresponding to a specific practical scheduling scenario. Based on the derived optimal properties, we develop an optimal algorithm for each of these cases. Finally, we consider a relaxed model of the second special case, and present a heuristic and analyze its worst-case performance bound.     

A mathematical programming-based scheduling framework for multitasking environments

A new paradigm along with a mixed (binary) integer-linear programming model is developed for scheduling tasks in multitasking environments, for which the number of completed tasks is not a good measure. One special case falls into the realm of deteriorating jobs. Polynomial time optimal solution algorithms are presented for this and one other special case. As the complexity of the original problem is believed to be strongly NP-hard, an efficient solution algorithm, based on tabu search, is developed to solve the problem. Small, medium, and large size problems are solved, and the solution obtained from the algorithm is compared with that of the optimal solution or the upper bound found from using the Lagrangian relaxation. Where it was measurable, the search algorithm gave quantifiably good quality solutions, and in all cases it had a much better time efficiency than the branch-and-bound enumeration method. A detailed statistical experiment, based on the split-plot design, is developed to identify the characteristics of the tabu search algorithm, thus guaranteeing a solution that is significantly better in quality. A conjecturing technique is introduced for problems with very large planning horizons. This technique had remarkable time efficiency with no apparent loss of quality.     

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

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

Bi-criteria scheduling problems: Number of tardy jobs and maximum weighted tardiness

Consider a single machine and a set of n jobs that are available for processing at time 0. Job j has a processing time p_j, a due date d_j and a weight w_j. We consider bi-criteria scheduling problems involving the maximum weighted tardiness and the number of tardy jobs. We give NP-hardness proofs for the scheduling problems when either one of the two criteria is the primary criterion and the other one is the secondary criterion. These results answer two open questions posed by Lee and Vairaktarakis in 1993. We consider complexity relationships between the various problems, give polynomial-time algorithms for some special cases, and propose fast heuristics for the general case. The effectiveness of the heuristics is measured by empirical study. Our results show that one heuristic performs extremely well compared to optimal solutions.     

The single machine batching problem with identical family setup times to minimize maximum lateness is strongly NP-hard

In this paper, we consider the single machine batching problem with family setup times to minimize maximum lateness. Recently, Cheng et al. [T.C.E. Cheng, C.T. Ng, J.J. Yuan, The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard, Journal of Scheduling 6 (2003) 483–490] proved that this problem is strongly NP-hard. This answers a long-standing open problem posed by J. Bruno and P. Downey [Complexity of task sequencing with deadlines, setup times and changeover costs, SIAM Journal on Computing 7 (1978) 393–404]. By a modification of the proof in Cheng et al. (2003), we show that this problem is still strongly NP-hard when the family setup times are identical.