HUGE Readme (E)

HUGE

(Version 3.01)

Abstract
Condition for use
Install
Implementation example (Single-user case)
Implementation example (Multiple-user case)
Data file
Limitations
Latest version
Acknowledgment

Abstract

HUGE is an interactive scheduling support system for flow- and job-shops. As HUGE is a Java application, it can be executable on many platforms with the aid of Java Runtime Environment.

Primal features of HUGE are as follows:

Five dispatching rules, i.e., SPT, LPT, MWKR, LWKR, and MOPNR are prepared to generate an initial schedule.
You can move the operations of the schedule displayed on the Gantt chart by using mouse.
You can "undo" the previous movement.
The schedule can be saved and re-read.
Data can be read from the remote host in addition to the local disks.
Schedule data can be shared by multiple users.

Condition for use

You can use the software without fee.
The software is copyrighted by Katsumi Morikawa.
The software is provided "AS IS", without a warranty of any kind.
We shall not be liable for correction of any bug.
You can re-distribute the complete and unmodified software to other people. However written permission is required to be included in the commercial media.
You can freely modify the software.

Please send any comment such as bug-report, improvement request, and question to the following mail address:

mkatsumi@hiroshima-u.ac.jp

Install

We assume that many people want to use the executable codes. If you need source files read the last part of this section. However we omit the explanation about methods of compiling and obtaining executable files from these source files.
First, obtain an appropriate Java executable environment or SDK of your platform. HUGE is developed by using Java 2 SDK, version 1.3 of Sun Microsystems, Inc. The latest version is available from Sun Microsystems, Inc., IBM, and other sites.
Then download appropriate file(s) based on your choice.
- Single-user case: HUGE.jar
- Multiple-user case: HUGE301.jar HUGE_Policy (Both files required)
Save these files onto your hard disk. If you want to see the source of the above executable files, the packed complete source file is here.

Implementation example (Single-user case)

To execute HUGE, simply double-click the downloaded file. However, if you are behind a firewall, you must enter the following command:
```
>java -Dhttp.proxyHost=proxyhost -Dhttp.proxyPort=portNumber -jar HUGE.jar [RETURN]
```
In this case, the speed of Open URL command becomes very slow.
Get a sample data. The downloaded file does not involve data file, therefore open Open URL... dialog from File menu. The default page:
```
http://home.hiroshima-u.ac.jp/mkatsumi/open/HUGE/data/index.html
```
will be displayed. By clicking "Three problems by Fisher and Thompson" and then "6-job, 6-machine problem", the corresponding problem is loaded. Now you can select a dispatching rule to generate an initial schedule. By clicking Generate button at the left bottom of the system, an initial schedule of this problem will be displayed.
(You can download data files on your disk by using your browser in advance. Then data can be read from Open file... dialog.)
If the displayed window is small, enlarge the window if you prefer. To change the scale of Gantt chart, click one of four buttons with triangle at the bottom right side. The unit scale of horizontal and vertical axes will be changed.
If your selection of dispatching rule is SPT, then the value of Cmax shown at the right bottom of the system will be 88. This value is the largest completion time of operations, and 88 is the completion time of the fourth operation of yellow-colored job J_B, in this problem.
In order to minimize the maximum completion time, it is generally required to move all operations to the left side. The current schedule has much slack, therefore let's try to modify the schedule.
First, click any yellow-colored box. Then the flow of job J_B from the first operation to the sixth operation is displayed by yellow lines. From this chart, we can find that the long waiting time exists between the second operation and the third operation. Therefore we try to move the third operation earlier.
Click Start button at the left-top corner of the system. Then the message: Select a box will be displayed at the bottom line. Click the yellow box of job J_B on machine M_4. The operation is the sixth operation to be processed on machine M_4. The clicked operation is highlighted, and the time interval is displayed with a bold line on the horizontal line. The starting time of the operation can be moved within the interval under the current schedule. In this case let's move the operation immediately after the red operation. By moving the mouse at the border of red box and light blue box, and click it, specified starting time is displayed at the bottom line, and you can now select Accept or Cancel buttons on the upper area. If you click Accept, then the revised new Gantt chart will be displayed. (Start, Accept, Cancel, and Undo can be implemented by pushing s, a, c, u key on the keyboard.)
It may happen that the red box is located after the yellow box in the revised schedule, if your pointed time is slightly earlier. In this case, click Undo button on the top of the system and obtain the previous schedule. Conduct the move operation again.
Tips: When you specify the start time of an operation, click the start time with holding down the SHIFT key, then the system calculates the ending time of the preceding operation, and assigns it as the start time of the target operation. This facility will be useful when you have difficulty assigning the accurate start time by the mouse.
In addition, specifying the star time of an operation with pushing CTRL key, the system assigns the start time of the operation as the earliest start time (start time of the movable interval displayed on the horizontal line).
Go back to the example. By moving the yellow job as the the second job to be processed on machine M_4, the value of Cmax will be improved to 79. However, you may find the machine M_5 will start the process of yellow operation at 55, in spite of the fact that it can be started at 42. By moving the operation at the earliest start time, the value of Cmax will now be 73.
Let's try to further improve the current schedule! The optimal value (minimum value) of Cmax for the current problem is 55.
Save the schedule if you can find a good schedule. Select Save... dialog from File menu. By entering the file name, problem data and the current schedule will be written to the specified file. If you load the saved file from Open file... dialog, then the saved schedule will be displayed.
In general the vertical axis of the Gantt chart is machine. However, it is also useful by assigning the job on vertical axis to see how jobs will be processed smoothly. Select Job or Machine from V-Axis to change the vertical axis.
If you do not satisfy the current color of jobs (or machines) displayed on the Gantt chart, then click the job (or machine) with right button of the mouse, then the color dialog will be displayed.
If all jobs have due date information, each due date will be displayed under the horizontal axis with corresponding color. (If vertical axis is job, then due date will be displayed for each job, separately.)
To print the current active Gantt chart, select Print from the File menu. To end HUGE, select Exit from the File menu.

Implementation example (Multiple-user case)

First, enter the following command at the directory where both HUGE301.jar and HUGE_Policy exist:
```
>jar -xf HUGE301.jar [RETURN]
```
When two or more schedulers use this system, one scheduler becomes 'Host', and the remaining all schedulers becomes 'Guest'. The host distributes the problem and schedules among schedulers, and the host can decide the distribution strategy of schedule data.
First, the host must execute the following command:
```
>start rmiregistry [RETRURN]
```
If you already set CLASSPATH, we think it is better to unset CLASSPATH before executing the above command.
Next, enter the following command: (for Windows users, we prepared a batch file describing this command.)
```
>java -Djava.security.policy=HUGE_Policy HUGE [RETURN]
```
A dialog will then be appeared. Enter your name, and ID (optional). The main HUGE window and a control window will be displayed. The guest then read a file from a local disk or web site.
On the other hand, the guest must enter the following command only:
```
>java -Djava.security.policy=HUGE_Policy HUGE [RETURN]
```
In this case, guest must enter the name of IP address of the machine running HUGE host program.
If both host and guests are ready, push Start button on the control window of the host. Then Data button on the control window of the guest will become selectable. By clicking the button, the data is transferred to the guest. All schedulers can see the performance of all schedulers, but the corresponding schedules can be viewed by guests if the host allow this action by clicking the checkbox of Share column.
Both host and guests can only have one scheduling problem. All schedulers can view other schedulers schedule by clicking View checkbox (if this operation is allowed by the host). However, his/her own schedule cannot dispose while the execution.

Data file

The following represents a simple 3-job, 3-machine, job shop scheduling problem:

<SCD1>
<DATANAME>
Sample 3-job, 3-machine problem.
</DATANAME>
<JOB>
JOB_A blue
JOB_B 0 255 255
JOB_C
</JOB>
<MACHINE>
MAC_1 yellow
MAC_2 pink
MAC_3 255 0 255
</MACHINE>
<OPERATION>
JOB_A MAC_1 4
JOB_A MAC_2 3
JOB_A MAC_3 2
JOB_B MAC_2 1
JOB_B MAC_1 4
JOB_B MAC_3 4
JOB_C MAC_3 3
JOB_C MAC_2 2
JOB_C MAC_1 3
</OPERATION>
<DUEDATE>
JOB_A 13
JOB_B 11
JOB_C 12
</DUEDATE>
</SCD1>

The data file must be enclosed by <SCD1> and </SCD1> block statements, and within this area, the following sub-blocks will be appeared in this order. <DATANAME> <JOB> <MACHINE> <OPERATION> <DUEDATE>, and <SCHEDULE>. Ending of each sub-block is declared by corresponding </...>. If the problem has no due date information, <DUEDATE> sub-block is not required. In addition, the sub-block <SCHEDULE> represents the generated schedule. Therefore it is generally not required to write this block manually. (The system automatically writes this sub-block when saving the schedule.)

Before discussing the detail of each sub-block, we explain some important restrictions.

Row is meaningful. Each (sub-)block statement must occupy one row. For example, a data file beginning with the following statement cannot be handled correctly:
```
<SCD1><DATANAME>
```
Each data described below must also be written in separate row.
Comment statement is not allowed to include in this version.
(Sub-)Block statement is case-insensitive. Therefore you can write <scd1> at the first row of the data. On the other hand, data section is case-sensitive.

<DATANAME> sub-block (required)

Data name or explanation.

<JOB> sub-block (required)

Job name and job color is specified in this sub-block. All jobs must be defined in this sub-block. The following 13 colors can be specified in string.

Standard 13 colors in Java: white, lightGray, gray, darkGray, black, red, pink, orange, yellow, green, magenta, cyan, blue.

In the above example, the color of JOB_A is blue. If you want other colors not listed above, specify the color in Red, Green, Blue by integer values within 0 to 255 in this order. In the above example, JOB_B is the case of this specification; Red:0, Green:255, Blue:255 gives cyan. If you omit the color information, the system automatically generates the color. Job name and color information must be separated by white space or tab code. These separator is also required between values when you want to specify colors by R, G, B.

<MACHINE> sub-block (required)

Same as the previous job sub-block.

<OPERATION> sub-block (required)

For each job, write the name of machine and process time separated by white space or tab code, in order of process. Integer values are only allowed as the process time. In the above example, job JOB_A must be processed first on machine MAC_1, and then processed by MAC_2, and lastly processed by MAC_3. The process times are 4, 3, 2, respectively.

<DUEDATE> sub-block (optional)

If data has due date information, then write the job name and due date separated by white space or tab code. Only integer values are allowed as due date. The system considers due date information only when all jobs have due date.

<SCHEDULE> sub-block (optional)

If you have a schedule, write the schedule in this sub-block in the order of machine name, job name, operation number, start time, separated by white space or tab code. The operation number is the integer value for each job starting from 1 to the number of operations. The following is an example of schedule sub-block. If data file contains schedule sub-block, the system automatically displays the specified schedule.

<SCHEDULE>
MAC_3 JOB_B 3 9
MAC_3 JOB_A 3 7
MAC_1 JOB_C 3 9
MAC_2 JOB_A 2 4
MAC_1 JOB_B 2 4
MAC_2 JOB_C 2 7
MAC_3 JOB_C 1 0
MAC_2 JOB_B 1 0
MAC_1 JOB_A 1 0
</SCHEDULE>

Limitations

All process times and due dates must be integer values. In addition, all jobs are assumed to be released to the shop at time zero.
If a data file contains SCHEDULE sub-block, the system does not confirm the feasibility of the schedule.
If the displayed Gantt chart is odd, please check your data file again. Our consistency test for given data file is very simple.
Color information of jobs and machines are saved in integer values of R, G, and B.
The length of job name and machine name is unlimited. But the first six letters are only displayed on the Gantt chart.
Due date related performance measures are calculated internally, but these values are not displayed on the screen.

Latest version

Latest version is available from my web site. Some famous job-shop scheduling problems and their optimal solutions are also available from my site.

Acknowledgment

Problems of job-shop scheduling are prepared based on the OR Library of Imperial College Management School.
Many optimal solutions of the job shop makespan minimization problems were prepared by Dr. Tsuyoshi Satake.

Apr. 21, 2001
mkatsumi@hiroshima-u.ac.jp