Due Date-Related Scheduling with Two Agents: Models and Algorithms (Uncertainty and Operations Research)

✍ Scribed by Yunqiang Yin, Dujuan Wang, T.C.E. Cheng

• Publisher: Springer
• Year: 2020
• Tongue: English
• Leaves: 198
• Category: Library

✦ Synopsis

This book provides an introduction to the models, methods, and results of some due date-related scheduling problems in the field of multiagent scheduling. In multiagent scheduling, two or more agents share a common processing resource and each agent wants to optimize its own objective function with respect to its own set of jobs. Since the agents have conflicting objective functions, they have to negotiate among themselves with regard to sharing the common resource to optimize their own objective functions. A key feature of due date-related scheduling concerns the way in which due dates are considered: they can be given parameters or decision variables. For the former case, the motivation stems from the need to improve inventory and production management. For the latter case, due date assignment becomes a challenging issue since the decision-maker has to balance inventory holding costs against the benefits of fulfifilling orders in time.

As for due dates, this book addresses the following three different scenarios: (i) The due dates of the jobs from either one or both of the two agents are decision variables, which are determined using some due date assignment models; (ii) The due dates of jobs in each job set are considered as given parameters, whereas which due date corresponds to a given job needs to determine; and (iii) The due date of each job is exogenously given. When the last case is involved, the objective function of each agent is related to the number of just-in-time jobs that are completed exactly on their due dates.

For each considered scenario, depending on the model settings, and on the objective function of each agent, this book addresses the complexity, and the design of efficient exact or approximated algorithms.

This book aims at introducing the author's research achievements in due date-related scheduling with two agents. It is written for researchers and Ph.D. students working in scheduling theory and other members of scientific community who are interested in recent scheduling models. Our goal is to enable the reader to know about some new achievements on this topic.

✦ Table of Contents

Preface
Acknowledgements
Contents
Acronyms
1 Introduction to Scheduling
1.1 Two-Agent Scheduling
1.1.1 Job Characteristics
1.1.2 Machine Environment
1.1.3 Objective Function
1.2 Due Date-Related Scheduling
1.2.1 Scheduling with Assignable Due Dates
1.2.2 Scheduling with Due Date Assignment
1.2.3 JIT Scheduling
1.3 Basic Scheduling Rules
1.4 Bibliographic Remark
2 Computational Complexity
2.1 Basic Concepts Related to Problems and Algorithms
2.2 Basic Concepts Related to Complexity
2.3 Exact Algorithms
2.4 Approximation Algorithms
2.5 Bibliographic Remark
3 Scheduling Problems with Assignable Due Dates
3.1 Integrating Optimization Method
3.1.1 Preliminary Analysis
3.1.2 Problem 1|d[j]A,d[j]B|γA+LmaxB
3.1.3 Problem 1|d[j]A,d[j]B|sumTjA+sumTjB
3.1.4 Problem 1|d[j]A,d[j]B|sumwjATjA+γB
3.1.5 Problem 1|d[j]A,d[j]B|sumwjAUjA+sumTjB
3.2 Constrained Optimization Method
3.2.1 Preliminary Analysis
3.2.2 Problems 1|d[j]A,d[j]B|γA:LmaxBleqQ
3.2.3 Problem 1|d[j]A,d[j]B|sumTjA:sumTjBleqQ
3.2.4 Minimizing Total Weighted Tardiness
3.2.5 Problem 1|d[j]A,d[j]B|sumUjA:sumUjBleqQ
3.2.6 Problem 1|d[j]A,d[j]B|sumwjAUjA:sumwjBUjBleqQ
3.2.7 Total Weighted Earliness and Tardiness
3.3 Summary and Tables
3.4 Bibliographic Remark
4 Scheduling Problems with Due Date Assignment
4.1 Due Date Assignment on the Jobs from Both of the Two Agents
4.1.1 Preliminary Analysis
4.1.2 The Linear Combination Optimization Problem
4.1.3 The Constrained Optimization Problem
4.2 DIF Due Date Assignment Method on A-Jobs
4.2.1 Problem 1|DIFA|sumj=1nA(εjA djA+βjAUjA):fmaxBleqQ
4.2.2 Problem 1|DIFA|sumj=1nA(εjA djA+βjAUjA):sumj=1nB UjBleqQ
4.3 CON/SLK Due Date Assignment Method on A-Jobs
4.3.1 Preliminary Analysis
4.3.2 Problems with the Criterion fmaxB
4.3.3 Problems with the Criterion sumj=1nBCjB
4.3.4 Problems with the Criterion sumj=1nBwjBCjB
4.3.5 Problems with the Criterion sumj=1nBwjBUjB
4.4 Summary and Tables
4.5 Bibliographic Remarks
5 Integrated Production, Inventory, and Batch Delivery Scheduling with Due Date Assignment
5.1 Due Date Assignment on the Jobs from Both of the Two Agents
5.1.1 Preliminary Analysis
5.1.2 Problems 1|D,Ba|γ1A:γ1BleqQ with Din{CON,DIF}
5.1.3 Problems 1|D,Ba|γ1A:γ2BleqQ with Din{CON,DIF}
5.1.4 Problems 1|D,Ba|γ2A:γ2BleqQ with Din{CON,DIF}
5.2 Due Date Assignment on the A-Jobs
5.2.1 Preliminary Analysis
5.2.2 Problems with γB=fBmax + mB ψBleqQ
5.2.3 Problems with γB=ωsumk=1nB CBk +mB ψB
5.2.4 Problems with γB=sumk=1nB βBk UBk + mB ψB
5.2.5 Computational Experiments
5.3 Summary and Tables
5.4 Bibliographic Remark
6 Scheduling Problems to Maximize the Weighted Number of JIT Jobs
6.1 Problems in the Two-Machine Flowshop Setting
6.1.1 Preliminary Analysis
6.1.2 The F2||(maxJkAinEAwkA,sumJkBinEBwkB) Problem
6.1.3 The F2||(sumJkAinEAwkA,sumJkBinEBwkB) Problem
6.1.4 Computational Experiments
6.2 Problems in the Unrelated Parallel-Machine Setting
6.2.1 Preliminary Analysis
6.2.2 The Rm||(sumJkAinEAwkA,maxJkBinEBwkB) Problem
6.2.3 The Rm||(sumJkAinEAwkA,sumJkBinEBwkB) Problem
6.2.4 Complexity Analysis
6.2.5 Concluding Remarks
6.3 Summary and Tables
6.4 Bibliographic Remark
References