具有恶化效应和共同工期窗口的极小化极大值单机排序问题

doi:10.16381/j.cnki.issn1003-207x.2020.2162

Abstract

Abstract:

Scheduling problems with deterioration effects （time-dependent processing times） have received increasing attention nowadays. In a real production environment， the processing time of each job often depends on its starting time， for example， a processing machine or a tool loses its qualities， i.e.， the later of a job starts， the longer it takes to process it， which is deterioration effect. In this paper， on one hand， the single machine scheduling problem is studied with a time-dependent deterioration model： the processing time of a job is proportional to its starting time， i.e.， $p j = a j (A + B s j)$ ， where $p j$ ， $s j$ ， $a j$ represent respectively， the actual processing time， starting time and deteriorating rate of the job $J j$ ， while A and B are given positive constants.On the other hand， under the Just-In-Time （JIT） system， jobs are required to be completed as close as possible to their assigned due-windows， otherwise， earliness or tardiness penalty would be incurred. Under common due-window put forward in this paper， the cost function is composed of earliness penalty， tardiness penalty， due-window starting time and size. The goal is to determine the starting time of the first job， schedule of jobs， due-window starting time and size so that the maximum cost function is minimized. It is showed that this minmax problem can be modeled by a linear programming. Some properties of the optimal solution are analyzed， which proved that the problem can be solved in polynomial time $O (n)$ ， where n is the number of jobs. Furthermore， a numerical example is given and the optimal solutions under different conditions are analyzed.Single machine minmax scheduling problem with deterioration effect and common due-window can impact the order in which the jobs are processed and thus affect production decisions. Therefore， it needs to take deterioration effect and due-window into consideration when making production decisions， and how to enhance production efficiency.

Key words: scheduling, minmax, due-window assignment, deterioration effect

CLC Number:

O223

Jing XUE,Ji-bo WANG. Minmax Scheduling with Deterioration Effects and Common Due-window on a Single Machine[J]. Chinese Journal of Management Science, 2023, 31(10): 187-192.

Figures/Tables 1

参考文献	研究问题	时间复杂度
Mosheiov^[15]	$1 p j m a x {λ m a x 1 ≤ j ≤ n E j, β m a x 1 ≤ j ≤ n T j, γ d 1, δ D}$	$O (n)$
Mosheiov^[15]	$P m p j m a x {λ m a x 1 ≤ j ≤ n E j, β m a x 1 ≤ j ≤ n T j, γ d 1, δ D}$	$N P -$ 难问题
Mosheiov和Sarig^[16]	$1 p j Z$	$O (n)$
Mosheiov和Sarig^[16]	$P 2 p j Z$	$O (n 2 l o g n)$
Gerstl和Mosheiov^[17]	$1 D W L m a x j = 1, . . ., n {λ E j + β T j + η X j + μ Y j}$	$O (n)$
刘春来等^[18]	$1 p j = a j s j Z$	$O (n l o g n)$
刘春来等^[18]	$F 2 p i j = a i j s i j C m a x$	$O (n 2 l o g n)$
罗成新和张庚^[20]	$1 p j r = (θ j r u j) k, ∑ j = 1 n u j ≤ U Z$	$O (n 3)$
罗成新和张庚^[20]	$1 p j r = (θ j r u j) k, Z ≤ Q ∑ j = 1 n u j$	$O (n 3)$
本文	$1 p j = a j A + B s j Z$
	①工期窗口位置和大小已知	$O (n)$
	②工期窗口大小已知	$O (n)$
	③工期窗口的开始时间已知	$O (n)$
	④工期窗口位置和大小未知	$O (n)$

References 22

1	Gupta J N D， Gupta S K. Single facility scheduling with nonlinear processing times［J］. Computers and Industrial Engineering， 1988， 14（4）： 387-393.
2	Alidaee B. A heuristic solution procedure to minimize makespan on a single machine with non-linear cost function［J］. Journal of the Operation Research Society， 1990， 41（11）： 1065-1068.
3	Kunnathur A S， Gupta S K. Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem［J］. European Journal of Operation Research， 1990， 47（1）： 56-64.
4	Wang Jibo， Gao Wenjun， Wang Liyan， et al. Single machine group scheduling with general linear deterioration to minimize the makespan［J］. The International Journal of Advance Manufacturing Technology， 2009， 43（1-2）： 146-150.
5	Miao Cuixia， Xia Yunjie， Zhang Yuzhong， et al. Batch scheduling with deteriorating jobs to minimize the total complete time［J］. Journal of the Operations Research Society of China， 2013，1（3）： 377-383.
6	苗翠霞，孟凡晓. 基于退化效应的两台机器流水作业可拒绝排序［J］. 运筹学学报， 2017， 21（2）： 66-72.
	Miao Cuixia， Meng Fanxiao. Two-machine flow-shop scheduling with deterioration and rejection［J］. Operations Research Transactions， 2017， 21（2）： 66-72.
7	Sun Xinyu， Geng Xinna. Single-machine scheduling with deteriorating effects and machine maintenance［J］. International Journal of Production Research， 2019， 57（10）： 3186-3199.
8	Huang Xue， Yin Na， Liu Weiwei， et al. Common due window assignment scheduling with proportional linear deterioration effects［J］. Asia-Pacific Journal of Operational Research， 2020， 37（1）： 1950031.
9	Gawiejnowicz S. Models and algorithms of time-dependent scheduling［M］. Berlin： Springer， 2020.
10	Kramer F J， Lee C Y. Common due-window scheduling［J］. Production and Operations Management， 1993， 2（4）： 262-275.
11	张扬，但斌，高华丽.带工期指派的产品服务系统订单随机调度问题研究［J］.中国管理科学，2019，27（2）： 93-106.
	Zhang Yang， Dan Bin， Gao Huali. Stochastic scheduling of product service system orders with due date assignment［J］. Chinese Journal of Management Science， 2019， 27（2）： 93-106.
12	Wan Guohua， Yen B P C. Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs［J］. European Journal of Operational Research， 2009， 195（1）： 89-97.
13	Yeung W K， Oguz C， Cheng T C E. Minimizing weighted number of early and tardy jobs with a common due window involving location penalty［J］. Annals of Operations Research， 2001， 108（1-4）： 33-54.
14	Sun Xinyu， Geng Xinna， Liu Tao. Due-window assignment scheduling in the proportionate flow shop setting［J］. Annals of Operations Research， 2020， 292（1）： 113-131.
15	Wang Jibo， Zhang Bo， Li Lin， et al. Due window assignment scheduling problems with position-dependent weights on a single machine［J］. Engineering Optimization， 2020， 52（2）： 185-193.
16	Mosheiov G. A due-window determination in minmax scheduling problems［J］. Information Systems and Operational Research， 2001， 39（1）：107-123.
17	Mosheiov G， Sarig A. Minmax scheduling problems with a common due-window［J］. Computers and Operations Research， 2009， 36（6）： 1886-1892.
18	Gerstl E， Mosheiov G. Minmax due-date assignment with a time window for acceptable lead-times［J］. Annals of Operations Research， 2013， 211（1）： 167-177.
19	刘春来，王建军，赵传立.具有退化工件和工期窗口安排的排序问题［J］. 运筹与管理， 2015， 24（4）： 116-121.
	Liu Chunlai， Wang Jianjun， Zhao Chuanli. Common due-date assignment and scheduling problems with deteriorating jobs［J］. Operations Research and Management Science， 2015， 24（4）： 116-121.
20	罗成新，张庚. 工期窗口指派可控处理时间资源约束最大费用最小化排序问题［J］. 重庆大学学报（自然科学版）， 2020， 37（1）： 52-59.
	Luo Chengxin， Zhang Geng. Minmax scheduling problem with common due-date and controlled processing times and resource restriction［J］. Journal of Chongqing Normal University （Natural Science）， 2020， 37（1）： 52-59.
21	Janiak A， Janiak W A， Krysiak T， et al. A survey on scheduling problems with due windows［J］. European Journal of Operational Research， 2015，242（2）： 347-357.
22	Kononov A. Single machine scheduling problems with processing times proportional to an arbitrary function［J］. Discrete Analysis and Operations Research， 1998， 5（3）： 17-37.

[1]	Song ZHAO,Zhe XU,Dong-ning LIU. Time/Cost Trade-off Problem in Decentralized Multi-project Scheduling [J]. Chinese Journal of Management Science, 2023, 31(9): 62-72.
[2]	XU Yin-feng, ZHI Rong-teng, ZHENG Fei-feng, LIU Ming. Online Strategy and Competitive Analysis of Production Order Scheduling Problem with Rental Cost of Shared Machines [J]. Chinese Journal of Management Science, 2023, 31(4): 142-150.
[3]	HE Pei-yang, LI Kun-peng, TIAN Qian-nan. The Integrated Production and Transportation Scheduling Problem Based on 3D Printing Technology [J]. Chinese Journal of Management Science, 2023, 31(4): 239-249.
[4]	ZHANG Ling-ling, WANG Ming-zheng. A Novel Model and Algorithm for Integrated Nurse Scheduling Considering Balanced Workload [J]. Chinese Journal of Management Science, 2023, 31(3): 177-185.
[5]	HU Xue-jun, WANG Jian-jiang, SUN Qing, BAI Jian, HAN Xue. Research on TT&C Scheduling Methods of Multi-satellites and Multi-stations Based on Maximal Cliques [J]. Chinese Journal of Management Science, 2023, 31(2): 73-83.
[6]	Wu-liang PENG,Liang-wei CHEN. A Program Cascade Optimization Scheduling Method [J]. Chinese Journal of Management Science, 2023, 31(10): 146-152.
[7]	LIU Ming, XU Xi-fen, NING Jing, CAO Jie. Modeling and Optimizing Method for Rebalancing the Dock-less Bicycles based on Order Data Analysis [J]. Chinese Journal of Management Science, 2022, 30(4): 275-286.
[8]	MA Zhi-qiang, XU Xiao-feng, HE Zheng-wen, WANG Neng-min. Robust Scheduling Optimization of Project Resources with Activity Splitting under Complex and Uncertain Environments [J]. Chinese Journal of Management Science, 2022, 30(3): 117-130.
[9]	LI Fei-fei, XU Zhe. Distributed Multi-project Stochastic Scheduling with Two-stage Coordination Mechanism of Resources Allocation [J]. Chinese Journal of Management Science, 2022, 30(12): 38-51.
[10]	SU Zhi-xiong, WEI Han-ying, ZHANG Jing-wen, QI Jian-xun. Optimization of a Type of Local Resource-Constrained Project Scheduling Problem Based on the Strong Duality Theory of Integer Programming [J]. Chinese Journal of Management Science, 2022, 30(11): 159-169.
[11]	XIE Fang, LI Hong-bo, BAI Qing-guo. Stochastic Multi-mode Resource-constrained Project Scheduling [J]. Chinese Journal of Management Science, 2022, 30(10): 155-164.
[12]	LIU Wei-bo, ZHANG Hao-yue, ZHANG Jiang-hua. Research on Cross-region Patient Scheduling Problem Considering Travel Time and Machine Setup Time [J]. Chinese Journal of Management Science, 2021, 29(9): 180-187.
[13]	CUI Wei-wei, TAN Xin-lin. Modeling and Approach for the Energy-aware Production Scheduling Problem under TOU Tariff [J]. Chinese Journal of Management Science, 2021, 29(5): 147-156.
[14]	ZHENG Fei-feng, JIN Kai-yuan, ZHANG E, LIU Ming. Online Two Parallel Batch Machines Scheduling with Order Types [J]. Chinese Journal of Management Science, 2021, 29(5): 173-179.
[15]	WANG Xiu-li, XU Yue, HU Xiu-wu. Modeling and Algorithm for a Monthly Shift Scheduling and Rostering Problem in Small-Size Call Centers [J]. Chinese Journal of Management Science, 2021, 29(4): 169-178.

Minmax Scheduling with Deterioration Effects and Common Due-window on a Single Machine

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 1

References 22

Related Articles 15

Metrics

Comments

Recommended 0