Customer Order Scheduling Problems on Parallel Machines with Job Capacity Restriction

Yang, Jaehwan 한국경영과학회 2003 Management Science and Financial Engineering Vol.9 No.2

We consider the customer order scheduling problem with job capacity restriction where the number of jobs in the shop at the same time is fixed. In the customer order scheduling problem, each job is part of some batch (customer order) and the composition of the jobs (product) in the batch is prespecified. The objective function is associated with the completion time of the batches instead of the completion time of the jobs. We first summarize the known results for the general customer order scheduling problems. Then, we establish some new properties for the problems with job capacity restriction. For the case of unit processing time with the objective of minimizing makespan, we develop a polynomial-time optimal procedure for the two machine case. For the same problem with a variation of no batch alternation. we also develop a polynomial-time optimal procedure. Then, we show that the problems with the objectives of minimizing makespan and minimizing average batch completion time become NP-hard when there exist arbitrary number of machines. Finally, we propose optimal solution procedures for some special cases.

Hybrid Flow Shop with Parallel Machines at the First Stage and Dedicated Machines at the Second Stage

Yang, Jaehwan Korean Institute of Industrial Engineers 2015 Industrial Engineeering & Management Systems Vol.14 No.1

In this paper, a two-stage hybrid flow shop problem is considered. Specifically, there exist identical parallel machines at stage 1 and two dedicated machines at stage 2, and the objective of the problem is to minimize makespan. After being processed by any machine at stage 1, a job must be processed by a specific machine at stage 2 depending on the job type, and one type of jobs can have different processing times on each machine. First, we introduce the problem and establish complexity of several variations of the problem. For some special cases, we develop optimal polynomial time solution procedures. Then, we establish some simple lower bounds for the problem. In order to solve this NP-hard problem, three heuristics based on simple rules such as the Johnson's rule and the LPT (Longest Processing Time first) rule are developed. For each of the heuristics, we provide some theoretical analysis and find some worst case bound on relative error. Finally, we empirically evaluate the heuristics.

A Special Case of Three Machine Flow Shop Scheduling

Yang, Jaehwan Korean Institute of Industrial Engineers 2016 Industrial Engineeering & Management Systems Vol.15 No.1

This paper considers a special case of a three machine flow shop scheduling problem in which operation processing time of each job is ordered such that machine 1 has the longest processing time, whereas machine 3, the shortest processing time. The objective of the problem is the minimization of the total completion time. Although the problem is simple, its complexity is yet to be established to our best knowledge. This paper first introduces the problem and presents some optimal properties of the problem. Then, it establishes several special cases in which a polynomial-time optimal solution procedure can be found. In addition, the paper proves that the recognition version of the problem is at least binary NP-complete. The complexity of the problem has been open despite its simple structure and this paper finally establishes its complexity. Finally, a simple and intuitive heuristic is developed and the tight worst case bound on relative error of 6/5 is established.

Heuristics for Flow Shop Scheduling with Weighted WIP Costs

Jaehwan Yang,Hyunsoo Kim 대한산업공학회 2006 대한산업공학회 춘계학술대회논문집 Vol.2006 No.5

No Tardiness Rescheduling with Order Disruptions

Yang, Jaehwan Korean Institute of Industrial Engineers 2013 Industrial Engineeering & Management Systems Vol.12 No.1

This paper considers a single machine rescheduling problem whose original (efficiency related) objective is minimizing makespan. We assume that disruptions such as order cancelations and newly arrived orders occur after the initial scheduling, and we reschedule this disrupted schedule with the objective of minimizing a disruption related objective while preserving the original objective. The disruption related objective measures the impact of the disruptions as difference of completion times in the remaining (uncanceled) jobs before and after the disruptions. The artificial due dates for the remaining jobs are set to completion times in the original schedule while newly arrived jobs do not have due dates. Then, the objective of the rescheduling is minimizing the maximum earliness without tardiness. In order to preserve the optimality of the original objective, we assume that no-idle time and no tardiness are allowed while rescheduling. We first define this new problem and prove that the general version of the problem is unary NP-complete. Then, we develop three simple but intuitive heuristics. For each of the three heuristics, we find a tight bound on the measure called modified z-approximation ratio. The best theoretical bound is found to be 0.5 - ${\varepsilon}$ for some ${\varepsilon}$ > 0, and it implies that the solution value of the best heuristic is at most around a half of the worst possible solution value. Finally, we empirically evaluate the heuristics and demonstrate that the two best heuristics perform much better than the other one.

Special Cases on Two Machine Flow Shop Scheduling with Weighted WIP Costs

Jaehwan Yang 한국경영과학회 2009 Management Science and Financial Engineering Vol.15 No.2

In this paper, we consider a relatively new two-machine flow shop scheduling problem where the unit time WIP cost increases as a job passes through various stages in the production process, and the objective is to minimize the total WIP (work-in-process) cost. Specifically, we study three special cases of the problem. First, we consider the problem where processing times on machine 1 are identical. Second, the problem with identical processing times on machine 2 is examined. The recognition version of the both problems is unary NP-complete (or NP-complete in strong sense). For each problem, we suggest two simple and intuitive heuristics and find the worst case bound on relative error. Third, we consider the problem where the processing time of a job on each machine is proportional to a base processing time. For this problem, we show that a known heuristic finds an optimal schedule.

7.Flow-shop Scheduling Problem with Weighted Work-In-Process

Jaehwan Yang 대한산업공학회 2005 대한산업공학회 춘계학술대회논문집 Vol.2005 No.5

Customer Order Scheduling Problem on Parallel Machines with Identical Order Size

Jaehwan Yang 한국경영과학회 2007 Management Science and Financial Engineering Vol.13 No.2

This paper considers a scheduling problem where a customer orders multiple products (jobs) from a production facility. The objective is to minimize the sum of the order (batch) completion times. While a machine can process only one job at a time, multiple machines can simultaneously process jobs in a batch. Although each job has a unique processing time, we consider the case where batch processing times are identical. This simplification allows us to develop heuristics with improved performance bounds. This problem was motivated by a real world problem encountered by foreign electronics manufacturers. We first establish the complexity of the problem. For the two parallel machine case, we introduce two simple but intuitive heuristics, and find their worst case relative error bounds. One bound is tight and the other bound goes to 1 as the number of orders goes to infinity. However, neither heuristic is superior for all instances. We extend one of the heuristics to an arbitrary number of parallel machines. For a fixed number of parallel machines, we find a worst case bound which goes to 1 as the number of orders goes to infinity. Then, a tighter bound is found for the three parallel machine case. Finally, the heuristics are empirically evaluated.

A New Complexity Proof for Two-Stage Hybrid Flow Shop Scheduling Problem with Dedicated Machines

Jaehwan Yang 한국경영과학회 2008 한국경영과학회 학술대회논문집 Vol.2008 No.5

This paper considers a two-stage hybrid flow shop scheduling problem with dedicated machines at stage 2. The objective is to minimize makespan. There exist one machine at stage 1 and two machines at stage 2. Each job must be processed on a machine at stage 1 and depending upon the job type, the job is processed on either of the two machines at stage 2. We first introduce this special two-stage hybrid flow shop scheduling problem and present some preliminary results. Then, we present a counter example to the known complexity proof. Finally, we re-establish complexity of the problem.

Customer Order Scheduling Problems with Fixed Machine-Job Assignment

Jaehwan Yang 대한산업공학회 2004 대한산업공학회 춘계학술대회논문집 Vol.2004 No.2