Optimal Algorithms Of The Scheduling Problem With Common Due Window

In order to eliminate hidden production and inventory problems which cause high costs, for example, waiting time, delivery time, extra labour costs, rework and order changes, manufacturers must consider scheduling problems involving not only the tardiness penalties, but also the early costs. They are JIT (Just-In- Time) sequencing and scheduling problems, which assume the existence of job due dates and discourage early as well as tardy jobs. If a job finishes before its due date, an early penalty will be incurred such as holding cost. And completing the job after it can result in such tardy penalty as late charge, express delivery charge, or lost of sale. So a JIT-schedule is to minimize the sum of these penalties.Under the Just-In-Time conception, it is desired to have jobs completed as close as possible to their respective due dates, or minimize the weighted number of early and tardy jobs. This necessitates the use of nontraditional performance measures that take into account both early and tardy events. Since its objective is non-regular about the completion time of jobs, the problem is more difficult and many related scheduling problems are NP-complete or even open.In this dissertation, we remove the common due date concept and replace it with a common due window assumption. The concept of due window is important since most due dates are specified with some tolerances. Then it is a time interval defined by an early due date e (also called window location) and a tardy due date d, where K = d- e is window size. Ones finishing in [e, d] have no penalty. Otherwise, they are subjected to early or tardy penalties, depending on completing before e or after d. And the window location and size are to be determined along with the optimal sequence, penalized by linear time cost 7 and 6 respectively, in some production situations. Thus, this concept generalizes the common due date assumption.The above problems are real-life problems, concerning some existing unexplored ones which need to be addressed. Owing to the worldwide increasing importance of the Just-In-Time concept with due date tolerance, due window scheduling problems are significant. To our surprise, only a couple of single machine due window scheduling problems so far have been solved. One of the reasons is probably attricted to its notorious intractable hardness. The purpose of this dissertation is twofold, one of which is to investigate this unexplored problem and another is to provide solution procedures.Roughly, there are two kinds of penalty functions. The first is on early-time and tardy-time penalties, i.e. proportional to the time difference from the due window, which is often called earliness and tardiness. This objective is more common and competitive. Kramer and Lee [52] analyze such problem and prove its NP-completeness for given due window. Then a polynomial algorithm is provided there for decision window location but without cost. [62], [64] and [79] study the problems with variable window location, decision window location and size, and decision window size respectively. The objective is to find the optimal due window and job sequence such that the penalty sum of earliness, tardiness and the cost of determing due window is minimized. As solving these problems, the positional weight is a powerful tool and then efficient algorithms are provided based on some optimal properties. In Chapters 2,3 here, we extend it to the due window scheduling with batching, but no use of positional weight.Another is about the weighted number of early and tardy jobs, rather than how early or how late they are. This sort of problems is significant and has many practical applications, for example, in chemical, drugs and collection of blood from donors. Yeung et al. [86] prove that the problem is NP-complete with variable window location, when the penalty factors are arbitrary integers. Further, polynomial algorithms are proposed for two special cases. As for this function, Chapters 4 study other several versions about decision or given window location and size. Chapters 5-7 extend them to batching operation, family setups and parallel machines, which generalize the results of Chapter 4 and those in [86]. But positional weight is not holden for this penalty function. The thesis is divided into the following seven chapters. In Chapter 1, we introduce due window scheduling and the related combinatorial optimization problems, some key concepts about complexity and related work about due dates and due window.In the previous references about batching, the optimal schedule is to minimize the total completion time or makespan. Only several consider the existence of due dates and make the total tardiness or maximal lateness minimized. In Chapters 2, 3, 5 of this dissertation, we firstly extend due window scheduling to the situation where the jobs can be processed in batches, where a batch is a set of jobs processed simultaneously and completed together when the processing of all jobs in the batch is finished. Thus, the task is to partition the jobs into batches and schedule the batches to minimize the sum of all costs. In Chapter 2, the scheduling problem associated with batching and common due window, is considered, but for unbounded batching. The objective is to minimize the total weighted earliness and tardiness penalties of all jobs, for given and decision window location.Property 2 There exists an optimal schedule a, where the batches in window set W(σ) contain the smallest jobs among all n jobs.Property 3 In any optimal schedule a, either W(σ) = 0 or it contains only one batch, whose processing time is the smallest of all batches.Property 6 In an optimal schedule, the batches in tardy set are sequenced in nondecreasing order of their processing times.Then for the given due window, the starting time of the first processed batch can be obtained as Property 5. Further, an optimal schedule is in SPT-batch rule, see Property 7. Thus the problem is transformed to minimize the total completion time of tardy jobs. So a dynamic programming is used to determine the tardy batches. For the decision window location e, its value is as Property 9, since the first processed batch starting at time zero. After enumerating the elements of W, it is also to minimize the total completion time of tardy jobs. Based on the above analysis, two optimal algorithms are generated, respectively in time O(n~2 logn) and O(n~3 logn), where n is the number of jobs.As for bounded batching with a given due window, it is discussed in Chapter 3 to minimize the weighted earliness and tardiness. But the complexity is NP-complete. Actually, this scheduling problem is more difficult than the one to minimize the total completion time, whose complexity is open and only PTAS is proposed. Then several structural properties are proposed. For an optimal schedule, it satisfies SPT-batch rule and the window set still contains the smallest jobs, as Properties 11, 12. The following is extended from the classical problem.Property 10 In an optimal schedule a, there exists one batch B such that C(B) = e or C(B) = d, unless the starting time of the first processed batch is zero.The following special cases are solved. When the early set is empty, it is to minimize the total completion time of tardy jobs after the enumeration of determining window set. So a PTAS can be obtained. Additionally, a polynomial time algorithm is developed as all processing times are equal.The above two chapters are about early-time and tardy-time cost, respectively for unbounded and bounded batching. As for the second penalty function, several production environments are investigated among the following chapters. In Chapter 4, the objective is to minimize the weighted number of early and tardy jobs for given due window, decision window size, and variable window location and size. Correspondingly, three efficient algorithms are provided based on some optimal properties.As the extension of the last chapter, bounded batch scheduling is discussed in Chapter 5 to minimize the number of early and tardy jobs with the window location cost. When the early and tardy penalty coefficients of the jobs are arbitrary and the window location is decision, the problem is shown to be strongly NP-complete, whose instance can be transformed from one of 3-Partition problem. Then several optimal properties are proposed. But an optimal schedule can no longer restrict to SPT-batch order for the entire schedule.Then three special cases are solved. Firstly when all early penalties are zero, the problem is converted to a scheduling with determined due date to minimize the penalty sum, which is also NP-complete. Then a dynamic algorithm is obtained in pseudo-polynomial time for it. Secondly, if the window location cost is zero, the problem is also NP-complete and the location of the due window can take arbitrary large value. A pseudo-polynomial time algorithm is gained through encasing jobs with maximum penalties into window set. Those show that the above two cases are ordinarily NP-complete. Additionally, when the early and tardy penalties are job-independent and asymmetric, the window batches contain the smallest jobs and the problem is solved by an efficient algorithm in time O(max{b~2n, n logn}). Thus the results of b = 1 in [86] are generalized to the batching scheduling.Many practical scheduling problems involve processing several families of related jobs on common facilities. A setup time is required at the start of the schedule and on each occasion when the machine switches from processing jobs in one family to jobs in another family. Just due to the family setup tasks, the problem becomes much more difficult. In [78], minimizing the early-time and tardy-time penalties is discussed with common due window and family setups. But the complexity is open even for e = 0. Since such environment is very prevalent, Chapter 6 considers the scheduling problem with family setups and decision due window to minimize the weighted number of early and tardy jobs. The objectives are to partition each family of jobs into several runs and then schedule the runs, together with the determination of due window.Obviously, the first family setup is processed at time zero, and no idle time is between jobs or between jobs and family setups. Additionally, Properties 31～34 construct an optimal schedule. From the point of some jobs contributed to the total penalty, synthetic balance is analyzed to determine their owing, as Algorithm 6-1 in time O(n~2) for decision window location.When the window location and size are variable, except for the above mentioned properties, an optimal algorithm is proposed based on the following properties.Property 23 If 6 < 7, then in any optimal schedule, e = 0.Property 25 In an optimal schedule a, ifδ≥γ+αand e≥1, then K = 0.Corollary 4 In an optimal schedule a, ifγ<δ<γ+αand e≥1, then K equals to 1 plus the sum of the processing time of the jobs and the setup times in W(σ)\{J_e}.Chapter 7 generalizes the common due window scheduling to parallel machines to minimize the weighted number of early and tardy jobs, which is the extension from due date and single machine situation. It is strongly NP-complete. If the window location penalty is zero, a PTAS is obtained as a direct corollary of multiple knapsack problem. Otherwise, it is also solved after establishing the partial schedule of early sets.Suppose that all jobs share a common due window, the main contributions of this dissertation are as follows.1. A batch processing machine is capable of processing several jobs simultaneously, as a batch, to improve efficiency. Thus we investigate batching scheduling problems on a single machine to minimize the weighted early-time and tardy-time penalties.(1) The unbounded version is considered, i.e. b≥n. Based on the properties proposed, optimal algorithms are presented for given or variable window location. This is the first time to discuss due window scheduling problem combined with batch-machine situation.(2) The capacity of one batch admits b jobs at most, where b < n. For the fixed due window, the problen is NP-complete. Then for two special cases, PTAS and a polynomial algorithm are obtained respectively. All these extend the results of [52].2. The objective is about the weighted number of early and tardy jobs.(1) For given due window, decision window size, and variable window location and size, three efficient algorithms are provided based on some optimal properties. However, [86] investigated the case with variable window location and fixed size.(2) Extending the results of [86] to batching scheduling, it is proved to be NP-complete strongly for arbitrary integer of penalty factors. Then three special cases are solved where pseudo-polynomial algorithms and a polynomial algorithm are developed.(3) The scheduling problem with common due window and family setups is considered. Based on the optimal properties, two optimal algorithms is presented for decision window location, and variable window location and size, which extend those of [86].(4) The common due window scheduling problem for parallel machines is addressed. For the window location penaltyγ= 0 andγ≠0, two PTAS-es are obtained.