Fluid approximation of a controlled multiclass tandem network

A two-station, four-class queueing network with dynamic scheduling of servers is analyzed. It is shown that the corresponding Markov decision problem converges under fluid scaling to a fluid optimal control model. The structure of the optimal policy for the fluid network, and of an asymptotically optimal policy for the queueing network are derived in an explicit form. They concur with the tandem μ-rule, if this policy gives priority to the same flow of customers in both stations. In general, they are monotone with a linear switching surface. This revised version was published online in June 2006 with corrections to the Cover Date.     

Surgical case scheduling as a generalized job shop scheduling problem

Surgical case scheduling allocates hospital resources to individual surgical cases and decides on the time to perform the surgeries. This task plays a decisive role in utilizing hospital resources efficiently while ensuring quality of care for patients. This paper proposes a new surgical case scheduling approach which uses a novel extension of the Job Shop scheduling problem called multi-mode blocking job shop (MMBJS). It formulates the MMBJS as a mixed integer linear programming (MILP) problem and discusses the use of the MMBJS model for scheduling elective and add-on cases. The model is illustrated by a detailed example, and preliminary computational experiments with the CPLEX solver on practical-sized instances are reported.     

Energetic reasoning and bin-packing problem, for bounding a parallel machine scheduling problem

This paper deals with an extension of energetic reasoning, using some efficient lower bounds of the bin-packing problem, to get tight lower bounds for the P|r _i , q _i |C _max. The link between P||C _max and bin-packing problem is well-known. Our purpose is to extend the use of efficient lower bounds of the bin-packing problem to P|r _i , q _i |C _max. We focus on some time-intervals, to compute the mandatory parts of activities within this time-interval and then to deduce an associated bin-packing instance. Thus, lower bounds of the bin-packing problem are used to get new satisfiability tests for the parallel machine problem. We also propose to extend the classical time-bound adjustments of release dates and deadlines to efficiently use bin-packing lower bounds. Experimental results that prove the efficiency of our approach on several kind of instances are reported.     

可中断半在线排序问题

讨论两台同型机上的可中断半在线排序问题,目标函数为极大化最小的机器完工时间Cmin.首先考虑已知所有工件的加工时间在p和rp(p＞0,r≥1)之间的情形,对任意的参数r,设计了最优半在线算法.接着,对已知最大工件加工时间的情形作了研究,得到了一个竞争比为5/4的最优半在线算法.     

A competitive and cooperative approach to propositional satisfiability

Propositional satisfiability (SAT) has attracted considerable attention recently in both Computer Science and Artificial Intelligence, and a lot of algorithms have been developed for solving SAT. Each SAT solver has strength and weakness, and it is difficult to develop a universal SAT solver which can efficiently solve a wide range of SAT instances. We thus propose parallel execution of SAT solvers each of which individually solves the same SAT instance simultaneously. With this competitive approach, a variety of SAT instances can be solved efficiently in average. We then consider a cooperative method for solving SAT by exchanging lemmas derived by conflict analysis among different SAT solvers. To show the usefulness of our approach, we solve SATLIB benchmark problems, planning benchmark problems as well as the job-shop scheduling problem with good performance. The system has been implemented in Java with both systematic and stochastic solvers.     

Two due date assignment problems in scheduling a single machine

We study two single-machine scheduling problems: minimizing the sum of weighted earliness, tardiness and due date assignment penalties and minimizing the weighted number of tardy jobs and due date assignment costs. We prove that both problems are strongly NP-hard and give polynomial solutions for some important special cases.     

Learning heuristics for basic block instruction scheduling

Instruction scheduling is an important step for improving the performance of object code produced by a compiler. A fundamental problem that arises in instruction scheduling is to find a minimum length schedule for a basic block—a straight-line sequence of code with a single entry point and a single exit point—subject to precedence, latency, and resource constraints. Solving the problem exactly is known to be difficult, and most compilers use a greedy list scheduling algorithm coupled with a heuristic. The heuristic is usually hand-crafted, a potentially time-consuming process. In contrast, we present a study on automatically learning good heuristics using techniques from machine learning. In our study, a recently proposed optimal basic block scheduler was used to generate the machine learning training data. A decision tree learning algorithm was then used to induce a simple heuristic from the training data. The automatically constructed decision tree heuristic was compared against a popular critical-path heuristic on the SPEC 2000 benchmarks. On this benchmark suite, the decision tree heuristic reduced the number of basic blocks that were not optimally scheduled by up to 55% compared to the critical-path heuristic, and gave improved performance guarantees in terms of the worst-case factor from optimality.     

Hybrid Rollout Approaches for the Job Shop Scheduling Problem

In this paper, we focus on heuristic approaches for solving the deterministic job shop scheduling problem. More specifically, a new priority dispatch rule and hybrid rollout algorithms are developed for approaching the problem under consideration. The proposed solution algorithms are tested on a set of instances taken from the literature and compared with other methods. The computational results validate the effectiveness of the developed solution approaches and show that the proposed rollout algorithms are competitive with respect to several state-of-art heuristics for solving the job shop scheduling problem. The author thanks Dr. Marco Mancini and Dr. Alessandro Tarasio for valuable suggestions about computational issues.     

Analysis of a simple Markovian re-entrant line with infinite supply of work under the LBFS policy

We consider a two machine 3 step re-entrant line, with an infinite supply of work. The service discipline is last buffer first served. Processing times are independent exponentially distributed. We analyze this system, obtaining steady state behavior and sample path properties. AMS Subject Classifications 60K25 · 90B22 I. Adan and G. Weiss: Research supported in part by Network of Excellence Euro-NGI. G. Weiss: Research supported in part by Israel Science Foundation Grant 249/02.     

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.