Solution strategies for multi-stage wafer probing scheduling problem with reentry

The multi-stage wafer probing scheduling problem (M-WPSP) with reentry is a practical variation of the parallel-machine scheduling problem. Since the M-WPSP involves multiple product families, to be processed on multiple stages, with various job due dates, ready times, reentry, serial and batch operations, sequential-dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problems. In this paper, we consider two strategies to solve the M-WPSP with reentry, where the total machine workload must be minimized. These two strategies incorporate a global planning mechanism, in advance, to determine the required stage due date of job at each process stage to prevent the due date problems occurring at the final stage. The sequential strategy schedules the jobs at the required stages according to the sequence of manufacturing process. The parallel strategy is designed specifically for the reentrant characteristic. To evaluate the efficiency of the proposed strategies, a set of test problems involving four critical factors, the product family ratio, the temperature-change consideration, the tightness of due dates, and the ready time, are designed to test the quality of solutions under two levels of workload.     

Algorithms for the wafer probing scheduling problem with sequence-dependent set-up time and due date restrictions

In this paper, we consider the wafer probing scheduling problem (WPSP) to sequence families of jobs on identical parallel machines with due date restrictions. The machine set-up time is sequentially dependent on the product types of the jobs processed on the machine. The objective is to minimize the total machine workload without violating the machine capacity and job due date restrictions. The WPSP is a variation of the classical parallel-machine scheduling problem, that can be transformed into the vehicle-routing problem with time windows (VRPTW). One can therefore solve the WPSP efficiently using existing VRPTW algorithms. We apply four existing savings algorithms presented in the literature including sequential, parallel, generalized, and matching based savings, and develop three modifications called the modified sequential, the compound matching based, and the modified compound matching-based savings algorithms, to solve the WPSP. Based on the characteristics of the wafer probing process, a set of test problems is generated for testing purposes. Computational results show that the three proposed modified algorithms perform remarkably well.     

The poset scheduling problem

Let P and Q be two finite posets and for each pP and qQ let c(p, q) be a specified (real-valued) cost. The poset scheduling problem is to find a function s: PQ such that _pP c(p,s(p)) is minimized, subject to the constraints that p in P implies s(p) in Q. We prove that the poset scheduling problem is NP-hard. This problem with a totally ordered poset Q is proved to be transformable to the closed set problem or the minimum cut problem in a network.This work was done in the fall semester of 1982 when the second author was visiting Cornell University. The first author was his research associate during that period.The first author was supported by National Science Council of Republic of China under Grant NSC73-0208-M008-08 when he wrote the final version of this paper.     

Meta-heuristic algorithms for wafer sorting scheduling problems

Wafer sorting is usually regarded as the most critical stage in the whole wafer probing process. This paper discusses the wafer sorting scheduling problem (WSSP) with total setup time minimization as the primary criterion and the minimization of the number of machines used as the secondary criterion. Although the need to consider multiple criteria in real-world WSSPs is widely recognized, the present study is the first attempt to investigate this argument with setups consideration. In view of the strongly NP-hard nature of this problem, three meta-heuristic algorithms—an ant colony system algorithm, a Genetic algorithm, and a Tabu search algorithm are proposed. The proposed meta-heuristics are empirically evaluated by 480 simulation instances based on the characteristics of a real wafer testing shop-floor and found to be very effective in terms of finding good quality solutions.     

The just-in-time scheduling problem in a flow-shop scheduling system

We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n³) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n³) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn²) time optimization algorithm.     

The hybrid flow shop scheduling problem

The scheduling of flow shops with multiple parallel machines per stage, usually referred to as the hybrid flow shop (HFS), is a complex combinatorial problem encountered in many real world applications. Given its importance and complexity, the HFS problem has been intensively studied. This paper presents a literature review on exact, heuristic and metaheuristic methods that have been proposed for its solution. The paper briefly discusses and reviews several variants of the HFS problem, each in turn considering different assumptions, constraints and objective functions. Research opportunities in HFS are also discussed.     

The grocery superstore vehicle scheduling problem

Scheduling the deliveries from a regional distribution centre (RDC) to large stores of a major retailer of fast moving consumer goods includes every possible vehicle routeing complexity. Usual constraints, like the size of the vehicle and the length of the driving day, apply. More importantly, loading feasibility is a major factor, with frozen goods being at the front, produce and perishable products in the middle, and groceries at the tail of the rear end loading vehicle. Moreover, these three product types have different time windows, determined store by store. Items like medium movers and alcoholic drinks may only be stocked at particular hub depots, from where they must be collected and then delivered to the retail outlets. Collections of salvage are made from the stores and goods from suppliers are backhauled to an RDC, which may not be the vehicle base. Then there may be trunking between RDCs. In this case study, deliveries and collections by vehicles at an RDC are presently scheduled by updating daily a basic plan prepared every 6 months, using the skills of an experienced distribution professional. A simulated annealing-based algorithm has been developed to speed up the process by circumventing the need for the skeletal schedule. In the application tested, the solution produced by the algorithm requires the same number of vehicles as actually used, although the total delivery time is slightly longer. Further improvements, particularly in the quality of the initial solution, may be possible by exploiting the problem structure in recognizable ways.     

The problem of single-beam probing of an unknown medium

We propose an algorithm for determining the shadows of unknown bodies inside an arbitrary medium probed by radiation only in one direction. We demonstrate a successful performance of the algorithm in the case that on a direct visualization (a photograph) the bodies under consideration are indistinguishable. We study the problem of overlapping the shadows of some objects by others and conclude that this circumstance can improve or worsen the quality of reconstruction depending on the radiation characteristics of the medium. The presented results of numerical experiments show good agreement between theoretical and computational methods.     

The basic cyclic scheduling problem with deadlines

The purpose of this paper is to study the latest schedule existence, calculation and properties of a basic cyclic scheduling problem with deadlines. First it is shown that, in the general case, a latest schedule exists but may be difficult to compute. Then we focus on a special case we call the optimal cyclic production problem. We derive an upper bound for the number of maximal-path values needed to compute the latest starting times and show the K-periodic structure of the latest starting time sequences.     

The one-machine just-in-time scheduling problem with preemption

This paper investigates the notion of preemption in scheduling, with earliness and tardiness penalties. Starting from the observation that the classical cost model where penalties only depend on completion times does not capture the just-in-time philosophy, we introduce a new model where the earliness costs depend on the start times of the jobs. To solve this problem, we propose an efficient representation of dominant schedules, and a polynomial algorithm to compute the best schedule for a given representation. Both a local search algorithm and a branch-and-bound procedure are then derived. Experiments finally show that the gap between our upper bound and the optimum is very small.     

The single-server scheduling problem with convex costs

Being probably one of the oldest decision problems in queuing theory, the single-server scheduling problem continues to be a challenging one. The original formulations considered linear costs, and the resulting policy is puzzling in many ways. The main one is that, either for preemptive or nonpreemptive problems, it results in a priority ordering of the different classes of customers being served that is insensitive to the individual load each class imposes on the server and insensitive to the overall load the server experiences. This policy is known as the cμ-rule. We claim and show that for convex costs, the optimal policy depends on the individual loads. Therefore, there is a need for an alternative generalization of the cμ-rule. The main feature of our generalization consists on first-order differences of the single stage cost function, rather than on its derivatives. The resulting policy is able to reach near optimal performances and is a function of the individual loads.     

An O(n2) algorithm for a controllable machine scheduling problem

A single-machine scheduling problem with controllable processingtimes is discussed in this paper. For some jobs, the processingtime can be crashed up to u units of time with the additionalcost c per unit of time crashed. The object is to find an optimalprocessing sequence as well as crash activities to minimizetotal costs of completion and crash. This problem is shown tobe polynomially solvable, and an O(n²) algorithm is given togetherwith the theoretical proof.     

Formulating and solving a multi-mode resource-collaboration and constrained scheduling problem (MRCCSP)

The main motivation of this study is to provide, for the first time, a formulation and solution for a class of production scheduling problems (as in cluster tools) characterized mainly by resource collaboration to perform an operation and while allowing batches and considering alternative production methods. We develop a formulation for the new problem and term it a multiple mode per operation, resource collaboration, and constrained scheduling problem (MRCCSP). Some of the important new characteristics we consider are: multiple products (families); multiple orders (jobs) per family; precedence restrictions among the operations that constitute a job; alternative modes for the performance of an operation (each of which needs a set of collaborating resources) may be defined; complementary and exclusive restrictions between operation-modes; batch production is allowed; and setup times may depend on sequence and batch-size. The objective of the MRCCSP is to minimize makespan. We formulate the MRCCSP as a mixed integer linear programming model, and acknowledging the considerable size of the monolithic formulation required, we prescribe a specific method to achieve size reduction. Finally, a customized branch and bound algorithm for optimally solving this problem is proposed and examined experimentally.     

A railway scheduling problem

It is discussed hown railway routes arriving regularly at some station should be scheduled to minimize the maximum waiting time for passengers changing trains.

---

Zusammenfassung In der Arbeit wird untersucht, wie man fürn Eisenbahnlinien, die in regelmä\igen Abständen in einem Bahnhof eintreffen, die optimale Reihenfolge erhält, so da\ die maximale Wartezeit für die Reisenden, die in den Zug einer anderen Linie umsteigen wollen, minimiert wird.

     

Master physician scheduling problem

We study a real-world problem arising from the operations of a hospital service provider, which we term the master physician scheduling problem. It is a planning problem of assigning physicians’ full range of day-to-day duties (including surgery, clinics, scopes, calls, administration) to the defined time slots/shifts over a time horizon, incorporating a large number of constraints and complex physician preferences. The goals are to satisfy as many physicians’ preferences and duty requirements as possible while ensuring optimum usage of available resources. We propose mathematical programming models that represent different variants of this problem. The models were tested on a real case from the Surgery Department of a local government hospital, as well as on randomly generated problem instances. The computational results are reported together with analysis on the optimal solutions obtained. For large-scale instances that could not be solved by the exact method, we propose a heuristic algorithm to generate good solutions.     

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.     

The course scheduling problem at Lufthansa Technical Training

Lufthansa Technical Training GmbH (LTT) performs training courses for Lufthansa Technik AG as well as for several other international airlines. Courses of about 670 different types are offered of which several hundred take place each year. The course scheduling problem faced by LTT is to construct a yearly schedule which maximizes the profit margin incurred while meeting a variety of complex precedence, temporal, and resource-related constraints. A “good” operational schedule should also meet a number of additional subordinate objectives. We formalize the problem and develop a heuristic scheme along with several priority rules, as well as a local search algorithm to determine well-suited weights for weighted composite rules. The operational planning situation of 1996 served as our major test instance; additional test instances were constructed by modifying this data. Several computational experiments were carried out to evaluate the performance of the algorithms. It turned out that the best so-found schedule is substantially better in terms of the profit margin incurred than the solution manually constructed by LTT.     

Restoring infrastructure systems: An integrated network design and scheduling (INDS) problem

We consider the problem of restoring services provided by infrastructure systems after an extreme event disrupts them. This research proposes a novel integrated network design and scheduling problem that models these restoration efforts. In this problem, work groups must be allocated to build nodes and arcs into a network in order to maximize the cumulative weighted flow in the network over a horizon. We develop a novel heuristic dispatching rule that selects the next set of tasks to be processed by the work groups. We further propose families of valid inequalities for an integer programming formulation of the problem, one of which specifically links the network design and scheduling decisions. Our methods are tested on realistic data sets representing the infrastructure systems of New Hanover County, North Carolina in the United States and lower Manhattan in New York City. These results indicate that our methods can be used in both real-time restoration activities and long-term scenario planning activities. Our models are also applied to explore the effects on the restoration activities of aligning them with the goals of an emergency manager and to benchmark existing restoration procedures.     

The crew timetabling problem: An extension of the crew scheduling problem

In some urban transportation companies driving periods are short when compared with the total duty time, leading to long non-driving periods that can be used as cover time. This paper presents the Crew Timetabling Problem, an extension of the Crew Scheduling Problem in which crew timetables are obtained by levelling the cover crew resources. An objective function for this problem is proposed in order to balance the number of driving and cover crews. A Lisbon Underground case study is used to illustrate the Crew Timetabling Problem. The problem is represented in a multigraph and solved by a tabu search-based heuristic.